General
AltaVista's video search was one of the first on the web, and is still good. Unlike most video search tools, AltaVista's has the advantage of showing a thumbnail image of each video. Additionaly, the results page shows the file name the URL of the page it is on, the duration of the video, and the dimentions (height & width). Also unlike most other video search tools, AltaVista lets you search for videos from several partner websites.
Search Help
AltaVista's video search uses the same syntax as their web search, so see that page for more information. There is also a field operator just for the video search: media:beaches will find pages with the word beaches that contain a video.