gistfile1.php

<?php
// Put this in your functions.php or in a separate plugin if you want to show all locaitons on one page
add_action( 'pre_get_posts', 'wpseo_local_show_all_locations' );

function wpseo_local_show_all_locations( $query ) {
	if( false == $query->is_main_query() || false == is_post_type_archive( 'wpseo_locations' ) ) {
		return;
	}
	
	$query->set( 'posts_per_page', -1 );
});

// Put this snippet in your archive-wpseo_locations.php file
$categories = array();
if ( have_posts() ) :
	while ( have_posts() ) : the_post();
		$terms = wp_get_object_terms( get_the_ID() );
		
		if( ! is_wp_error( $terms ) ) {
			// We use the slug now as key for the array, so we can sort the categories alphabetical.
			// Use anything else (for example the term_id) if you need another type of sorting
			$categories[ $terms[0]->slug ][] => $post;
		}
	
	endwhile;
endif;

// Sort the categories by key (which is the slug now in this example)
ksort( $categories );

// Loop through the $categories and show the locations
foreach ( $categories as $category => $locations ) {
	echo '<h2>' . esc_attr( $category->name ) . '</h2>';

	foreach ( $locations as $location ) {
		echo get_the_title( $location->ID );
		echo wpseo_show_addres();
	}
}
?>