Theora

Theora is the preferred video codec for the OLPC.

You can encode Theora files using the commmand line application [ffmpeg2theora].

[VLC], the free media player software can also encode Theora files.

Colinog's wiki contains an entry on how to encode your video in Theora and in Theora/Speex. Translation and walkthrough for this space to come.