In an effort to help users search all the world's public videos, the Google Video team announced support for Video Sitemaps—an extension of the Sitemap Protocol that helps make your videos more discoverable via Google Video Search.

"By submitting this video-specific Sitemap in addition to your standard Sitemap, you can specify all the video files on your site, along with relevant metadata." - said Google

Example Video Sitemap:

<urlset xmlns="http://www.sitemaps.org/schemas/sitemap/0.9"
     xmlns:video="http://www.google.com/schemas/sitemap-video/1.0">
<url>
<loc>http://www.example.com/videos/some_video_landing_page.html</loc>
<video:video>
   <video:content_loc>http://www.example.com/video123.flv</video:content_loc>
   <video:player_loc allow_embed="yes">http://www.example.com/videoplayer.swf?video=123</video:player_loc>
   <video:title>My funny video</video:title>
   <video:thumbnail_loc>http://www.example.com/thumbs/123.jpg</video:thumbnail_loc>
</video:video>
</url>

<url>
<loc>http://www.example.com/videos/some_other_video_landing_page.html</loc>
<video:video>
   <video:content_loc>http://www.example.com/videos/video1.mpg</video:content_loc>
   <video:description>A really awesome video</video:description>
</video:video>
</url>
</urlset>

Instructions for video sitemaps can be found at Google Webmaster Tools