Help with Video Sitemap

Hello I need some help with a video sitemap. I have about four videos that I want to create a video sitemap for. First what is the best way to host these videos on my website so that they play quickly - next do I have to create a new page for each video or can I just add them to related pages.

Finally how do I create the sitemap, im no techie so could some one give me the raw code...

Thanks