Brett Tabke, the force behind WebmasterWorld, offered his own personal tips for online video at PubCon 2007, a reknowned SEO conference he hosts annually:

Use metadata where ever you can. Don’t skimp on doing the work to title, describe and tag your videos in every way that every platform you upload to provides.

Use logos in your videos. The Search Engines maintain files of logos in their image libraries. Using logos in your videos helps them make appropriate associations.

An hour of video will take an hour of production time. For each hour of video you end up with, expect to spend an hour in producing, tagging and uploading.

Check out Everyzing. Their software takes audio, turns it into text and puts it back up on the web as part of your video. This is very powerful in optimizing your videos.