Sorting terms individually for each post

For your first question:

— Where do I have to put the »HTML for the term order metabox«?

Take a look at the add_meta_box codex page, the example there shows you how to put a metabox on your posts admin pages.

Regarding your second question:

— Does the »JavaScript to make the above list sortable and save the order using ajax« has to be enqueued like so?

You should be using admin_enqueue_scripts, from within a plugin. Something like this:

function my_admin_scripts(){
  // js
  wp_enqueue_script( 'my_admin_js', plugins_url('myPlugin/js/my_admin.js') );
}
add_action( 'admin_enqueue_scripts', 'my_admin_scripts' );

Both of these bits of code should be called from a plugin. WordPress has a guide to creating plugins at Writing a Plugin