Video Embed in Sidebar Widget with Links to Others in Category

I would create a Custom Post Type for Videos, and use in conjunction with some plugin like Simple Video Embed

From there you can make a list of videos like so:

<?php query_posts('post_type= videoss','showposts=20'); ?>
<?php if (have_posts()) : while (have_posts()) : the_post(); ?>
              <div class="vidoes" > 
                        <?php echo p75GetVideo($post->ID, 400); ?>
            <h5><?php the_title(); ?></h5>
              </div>
            <?php endwhile; endif; ?>

That will give you a list of videos with the title underneath each one. It looks like that widget uses javascript to swap out the videos.