Apple refuses to implement Ogg Theora in Quicktime by default (as used by Safari), citing lack of hardware support and an uncertain patent landscape.
Google has implemented H.264 and Ogg Theora in Chrome, but cannot provide the H.264 codec license to third-party distributors of Chromium, and have indicated a belief that Ogg Theora's quality-per-bit is not yet suitable for the volume handled by YouTube.
Opera refuses to implement H.264, citing the obscene cost of the relevant patent licenses.
Mozilla refuses to implement H.264, as they would not be able to obtain a license that covers their downstream distributors.
Microsoft has not commented on their intent to support <video> at all.
What this is about is making it as easy to embed a video in a web page as it is to add a still image.