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(); ?>