To build a Firefox with this support, get the latest trunk CVS source. Apply the patch from bug 382267, followed by the patch from bug 422540. Build with the --enable-gstreamer configure option. Or follow these steps to build from the git repository.
I've made a prebuilt binary for Linux which you can download from firefox-3.0pre-video.en-US.linux-i686.tar.bz2.
With this build, when you visit a page that uses <video> it will use the GStreamer codecs available on your system to decode and play them. The Theora examples on my test page continue to work, and I've also tested it decoding H.264 videos in .mp4 and .mov files, using the Fluendo plugins.