Wow, that's great news! At first I thought you were just talking about normal sitemaps, but you're right, they just created the option of making video sitemaps. Man, I've been wanting to get my videos on google's video search for forever, and this looks like they're finally making it possible.
As for how to generate the sitemaps, Autodafe created a sitemap generator for vshare a while back (viewtopic.php?f=8&t=1839). I just pm'd him to see if he's willing to amend his sitemap generator to allow for the new functions needed for the video sitemaps. Otherwise, maybe someone else knows how to create a sitemap generator (I haven't got a clue). And if not, we'll just have to wait until some websites start popping up with the ability to generate video sitemaps, which I'm sure won't be more than a few weeks from now.
Thanks for the head's up Chadon.