I'd follow incredible's advice. It's about links mostly. However, the page the video is in also needs to be optimized. I don't know (yet) how much it helps to use the bits of technical options to indicate the content of the video, but you can be pretty sure that information that´s not visible to the user gets little attention. (just think of meta keyword tags, stuff that´s not visible to the users gets abused and is for that reason not that useful to a search engine.)
So it is more likely that they use techniques similar to image search to figure out the content of a video and rank them accordingly.
But there's a problem in search engine land. The search engines don't really know (yet) how to rank videos, so they use the "old" techniques and apply them to this new type of content that they have to rank because it is way too popular to ignore (much different in case of flash for example). The result is that pretty much only video websites like YouTube show up in the video results.
If you use the -site:youtube.com operator you can filter out the youtube results. Then you need to do something like this: shoes -site:youtube.com -site:google.com -site:myspace.com -site:metacafe.com -site:yahoo.com -site:expotv.com in order to get to results that are not in video sites but in normal websites.
It's going to take time for the search engines to learn how to rank video properly. But they will get better at that, especially when there will be more video online in normal websites. Right now, probably 99.99999999% of online videos can be found in video websites like YouTube and those videos get most of the backlinks. But that´s normal
PR logic. The Video Pagerank article that Webnauts linked to shows already that normal
PR isn't very useful in video search.
So optimize your video pages, don't try to optimized the video itself through the use of some tags that can't be seen by the visitor. Then get links to it and see if you can get your video high up in the video SERP's.
Actually I don't think it is really that difficult. You´re in a niche and competition is small. The only real competition you have is YouTube and even though they´re very big and known, they´re not relevant in your niche.