Google actually has a very good overview of creating XML video sitemaps. You can create a sitemap for your videos even if they are hosted by YouTube.
From the page: "Video content includes web pages which embed video, URLs to players for video, or the URLs of raw video content hosted on your site."
You can add video extension tags in your existing site, or create a standalone sitemaps just for videos. Also, you can submit the sitemap through the wonderful Webmaster Tools.
Good luck!