The Google Webmaster Central blog has announced Google Video Sitemaps. An extension of the Sitemap Protocol that helps make your videos more searchable 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. All you need to do is create a video sitemap and submit it to Google (it would be pretty easy if you have them organized, especially in a database). Google crawls a variety formats of videos, from MPEG to WMV to RM to FLV. There are some restrictions on the sitemaps and videos though, you can find them here.