@xaios: initially, the HTML5 draft explicitly recommended Ogg Theora and Ogg Vorbis (as being patent-unencumbered, free of charge to implement, open source in the public domain - you can't make it more free than that).
Due to opposition from Nokia and Apple, these were removed. Current HTML5 draft doesn't define a codec nor a container format, but you can define several streams if one doesn't work.
the current solution is thus:
- Safari ships with a built-in H.264 and AAC decoder, which are under license. It will only decode these formats. Safari ships on Mac and Windows.
- Chrome ships with Theora, Ogg, H.264 and AAC decoders built-in, and will decode all of them; H.264 and AAC are under license. Chrome ships on Mac, Windows and Linux, but is still beta on the *NIX OSes.
- Firefox ships with Theora and Vorbis, as does Chromium (the open source version of Chrome), which are license-free. It ships on pretty much any platform you may think of, and mobile editions also support Ogg and Theora.
- Opera still has this feature in beta.
A solution under consideration by most browser makers is to rely upon the video platform provided by the OS (ActiveX/Media Player on Windows, Quicktime on Mac, gstreamer,xine,mplayer etc. on Linux) to do the actual decoding, but since this is still very much in flux, currently they simply provide their internal video interfaces.
Ideally, all browsers (including free ones) will be able to decode any format (including those under license) provided a codec for it (either a system one or an internal one) is installed.
If x264 (the Free H.264 implementation) wasn't illegal in some countries, Firefox would support H.264. Please also note that recent Theora encoders are getting very close to H.264's encoding quality/compression (previously, some tests made with a faulty version of Theora created washed out video with a high bitrate), and that Theora was designed so that an encoder improvement may not require a decoder modification or specific implementation (this is what bit MP3 in the arse, for those of you who remember when LAME' Variable Bitrate caused quite a stir).