First of all: Embedding videos into HTML pages seems to be one of the most complicated things there are. Netscape introduced the embed-tag with theit Navigator 2.0 but it never became part of the html standard.
Moreover a patent exists that forced Microsoft to implement embed even more complicatedly.. But there is an existing JavaScript-solution that functions as a nice work-around.
There are several reasons that make Flash Video the best choice for the video encoding: The quality is good enough for most purposes and the flash plugin is the most common. Every other method is limited to an operating system (wmv -> Windows) or to rarer plugins (Real, Quicktime aso.) Jeroen Wijering wrote a nice article about Flash Video.
I used Riva FLV Encoder 2 for the encoding. It is free and supports the codecs I needed.
Jeroen Wijering not only wrote an article about FLV he also wrote the Flash Video Player which can be used to embed the videos into your site.
I use Pagesetter to store the metadata. My publication type has three fields: title, description and filename. Filename is im my case also a string because the videos are too big to upload them via HTML forms. We upload them into a predefined directory and only enter the filename into the form field.
The flashplayer is stored inside the themes folder:
themes/myTheme/flash/flash_flv_player
And you have to add a javascript call to the site's header:
[code][/code]
The -list.html-template of the publication type looks something like this:
[code]
I think this is a basis that should allow you to build your own video publication type. It's not too complicated and it works on several platforms and with several browsers.