For example, by trying to use the codec that is provided by the underlying operating system. The latest versions of both Windows and OS X ship with a H264 codec.
The real problem is non-commercial desktop distributions such as Debian or Fedora; it could still check for the presence of x264 or FFmpeg (with h264 support) on the system and use it if it's available, and defer the responsibility of licensing to the user or distributor.
Even if it couldn't, why would it be a bad thing for Firefox to support OS-supplied codecs on OS X and Windows, and a set of built-in codecs, such as WebM, on Linux?