My team did a lot of research on this in the past and
Theora came out as prime choice, mainly because of its BSD-style license.
Dom previously posted that the pi has software (but still vector accelerated) decoding support for theora.
From the theora.org website:
Theora (and all associated technologies released by the Xiph.org Foundation) is released to the public via a BSD-style license. It is completely free for commercial or noncommercial use. That means that commercial developers may independently write Theora software which is compatible with the specification for no charge and without restrictions of any kind.
Decoding video using Theora is fairly straightforward, we spent/lost more time on writing decent YUV to RGB conversion code to display the video in OpenGL. There might be a shortcut you can find in that area.
Displaying video in your app is a lot more involved then displaying an image because you have to deal with timing, but in practice you just decode frames to a texture, which you can then render on-screen.
Dave Driesen
Linux dev and oldskool elite