Notes on encoding with libtheora
The documentation for libtheora and some of the tools that use it is generally pretty good. But some applications don't provide their own documentation, and there are some points that people should still be reminded of even after reading the documentation.
Speed and quality
If you need really high speed and don't care if the bitrate is enormous (or the quality is really poor) you can use speed level 2. The purpose it was created for was from keeping video encoding from falling behind on the OLPC. A live encoder could temporarily switch to it to catch up, for example. But because it disables half of the format, the quality is really terribly except at very high bitrates.
Rate control and quality
Another piece of advice is that by default one pass rate control imposes a buffering constraint: It does not allow the instantaneous bitrate to go above what could be satisfied by a small buffer. This is important for real time streaming, but it can be absolutely brutal on the quality. Two-pass does not, because other video formats used in infinite latency applications don't do any buffer constraint. You can use the buf-delay knob to control the amount of buffer constraint.
Encoder_example peculiarities
Theora uses the JPEG chroma siting. Encoder_example will automatically resample non-jpeg sited input to the JPEG positions. This can be surprising if you don't know that it does it.
Like many other formats Theora must encode an area that is a multiple of 16x16 pixels. If you have a video that isn't a multiple of that size the tools round up then leave a note in the format to tell the decoder to crop down. All tools do this.
Theora has an offset header that allows the cropped header to be some-place other than in one extreme corner of the video. A few decoder tools (e.g. mplayer, ffmpeg) have ignored this offset parameter and sometimes the crop parameter, causing offset videos to come out slightly shifted.
Encoder_example always centers the video. This makes people more likely to notice offset-broken decoders. It does, unfortunately, seem to reduce quality for some clips because of how the invisible area can interact with motion prediction.
Regardless of the encoder used you're best off it you can choose sizes which are a multiple of 16x16.
The most current Theora encoder
You also might want to try out the current encoder rather than the older stuff. It's available from SVN at http://svn.xiph.org/experimental/derf/theora-ptalarbvorm/ and can also be used with ffmpeg2theora.
Compared to 1.1, the new encoder produces nicely improved visual results though watch out because the visual optimizations are not good for PSNR (though they do enormously improve SSIM).