Matroska

Matroska is a new multimedia container format usually found as .mkv files (matroska video) and .mka files (matroska audio).

This high-end container format supports fast seeking, embedded chapters and subtitle, several video and audio tracks, and supports latest codecs like H.264 and AAC (I highly recommend to encode your videos with these for quality reasons).
Unlike other container formats like AVI, you can easily switch between subtitle or audio tracks during playback and stream it over RTP.
In the near future it will also include menu support like found on DVDs.

Tools

To create such a multimedia stream the best tool is MKV-Toolnix, a graphical user interface for the mkvmerge program, which allows to create Matroska files from other formats.
It can be found for Windows and for Linux.

Install instructions for Ubuntu Hardy

The following instructions will install the latest version, not the old one which is found in the official Ubuntu repository.

sudo -s
echo "deb http://www.bunkus.org/ubuntu/hardy/ ./ #MKVToolNix - Cross-platform tools for Matroska
deb-src http://www.bunkus.org/ubuntu/hardy/ ./ #MKVToolNix - Cross-platform tools for Matroska" > /etc/apt/sources.list.d/bunkus.list
wget -q http://www.bunkus.org/gpg-pub-moritzbunkus.txt -O- | apt-key add -
aptitude update
aptitude -y install mkvtoolnix-gui
exit