How to create a custom loop ordered by Categories on a Page Template?

Not sure if this is exactly what you’re asking, but it sounds like you’re looking for nested loops. This will list the most recent 5 posts in every category on your site:

foreach ( get_terms('category') as $category ) {

    echo '<h2>'.$category->name.'</h2>';
    echo '<ul>';

    foreach ( get_posts( 'cat=".$category->term_id ) as $post ) {
        setup_postdata( $post );
        echo "<li><a href="'.get_permalink($post->ID).'">'.get_the_title().'</a></li>';

    }
    echo '</ul>';
} 

Add the name of the custom post type and any other variables you may want to modify the loop with to the call to get_posts. You can look through the Codex page for a list of argument that can be passed.