Then just check when the post type changes, and display whatever header you like.

Then just check when the post type changes, and display whatever header you like:

<?php
$post_type = '';
while (has_posts()): the_post;

if (get_post_type() !== $post_type) {
    // print the header for the post type
    // maybe something like this...
    echo '<h2>', esc_html(get_post_type_object(get_post_type())->label)), '</h2>';
}

// do stuff with the current post

$post_type = get_post_type();

endwhile;

Hook into pre_get_posts, check for the taxonomy, and set all four post types as the post_type parameter of the query object. Check out the Type Parameters section on the WP_Query docs for more information.

<?php
add_action('pre_get_posts', 'wpse87225_set_post_types');
function wpse87225_set_post_types($query)
{
    if (is_admin() || !$query->is_main_query() || !is_tax('destination')) {
        return; // bail, not where we want to be
    }

    $query->set('post_type', array(
        'Deals', 'Accommodation', 'Attractions', 'Articles'));
}

Hook into pre_get_posts, check for the taxonomy, and set all four post types as the post_type parameter of the query object. Check out the Type Parameters section on the WP_Query docs for more information.

<?php
add_action('pre_get_posts', 'wpse87225_set_post_types');
function wpse87225_set_post_types($query)
{
    if (is_admin() || !$query->is_main_query() || !is_tax('destination')) {
        return; // bail, not where we want to be
    }

    $query->set('post_type', array(
        'Deals', 'Accommodation', 'Attractions', 'Articles'));
}

The above could go in your functions.php file, or, more appropriately, a plugin.

Edit to address the group by requirement:

That's not going to split them up, however. There a few options to do that. First, you could just leave the main query alone (don't do the above), and create multiple instances of WP_Query and do multiple loops. Not bad.

You could also hook into posts_orderby and alter the SQL to order the posts by post type as well as whatever else is there:

<?php
add_filter('posts_orderby', 'wpse87225_posts_orderby', 10, 2);
function wpse87225_posts_orderby($orderby, $query)
{
    global $wpdb;

    if (is_admin() || !$query->is_main_query() || !is_tax('destination')) {
        return $orderby;
    }

    $new = "{$wpdb->posts}.post_type ASC";

    if ($orderby) {
        $orderby = $new . ', ' . $orderby;
    } else {
        $orderby = $new;
    }

    return $orderby;
}

You could even be very granular and order by specific post type with the help of the FIELD function.

<?php
add_filter('posts_orderby', 'wpse87225_posts_orderby', 10, 2);
function wpse87225_posts_orderby($orderby, $query)
{
    global $wpdb;

    if (is_admin() || !$query->is_main_query() || !is_tax('destination')) {
        return $orderby;
    }

    $new = "FIELD({$wpdb->posts}.post_type, 'Deals', 'Accommodation', 'Attractions', 'Articles') ASC";

    if ($orderby) {
        $orderby = $new . ', ' . $orderby;
    } else {
        $orderby = $new;
    }

    return $orderby;
}

Then just check when the post type changes, and display whatever header you like.