Theora

Theora is the preferred video codec for the OLPC.

Recommended settings

[This file] plays back well on a B4 laptop, running build 623. Ogg multiplexed audio/video file, Theora/Vorbis, length 1m14s, 320×240 pixels, 148kbps overall.

Useful Encoding software

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.