WordPress custom post type and taxonomy

As per Anand’s comment, something like this should work.

<?php get_header();?>

<?php
    $args = array( 'post_type' => 'Video');
    $loop = new WP_Query( $args );

    $old_term = null;
    while ( $loop->have_posts() ):
        $loop->the_post();
        $fg = get_the_terms(get_the_ID(),'category');
        foreach($fg as $term):
            if ( $old_term === null || $old_term != $term ):
                $old_term = $term;
?>
                <h2><?php echo $term->name; ?></h2>
<?php
            endif;

            $posts = new WP_Query(array('post_type' => 'Video', 'category' => $term->name) );
            while ( $posts->have_posts() ) : $posts->the_post();
                the_post_thumbnail();
?>
                <a href="https://wordpress.stackexchange.com/questions/38968/<?php the_permalink(); ?>"><?php the_title(); ?></a>
<?php
            endwhile;

            wp_reset_postdata();
        endforeach;
    endwhile;
?>

<?php get_footer(); ?>