The FFmpeg tool and associated libraries (as of Natty, Ubuntu has switched from FFmpeg to the libav fork) is the premier video decoding and encoding system on Linux (and in computing in general).
The ffmpeg tool is a command line program that can be used to encode from one of many dozen codecs/formats into a similar number of other formats. The libraries from the project are available for developers to use in their own programs to provide video codecs, formats, devices, filters, scaling, and post-processing.
Due to patent restrictions for some countries, there are several levels of support for various codecs and formats within Ubuntu’s FFmpeg/libav packages.
