This is if you have a separate text file (for example, an .srt file) with the subtitles, and you want to add them to the video stream. Note that your subtitle file has to contain text, not images (here's a list of common subtitle file formats).

You can use mencoder for this, which is part of the mplayer package (get mplayer here).

subtitle font

Make sure there is a font for subtitles in your ~/.mplayer directory, to check:
ls -l ~/.mplayer/subfont.ttf

If there isn't, you can locate TrueType fonts on your system as follows:
locate ttf | grep ttf\$

If that command doesn't work, then maybe you've never run updatedb, so run it (as root), and try again.

Pick a font that sounds reasonable, for example /usr/share/fonts/bitstream-vera/Vera.ttf and copy it:
cp /usr/share/fonts/bitstream-vera/Vera.ttf ~/.mplayer/subfont.ttf

You can see what the font looks like by running:
mplayer -sub mymovie.srt mymovie.avi
(note that you don't have to specify the name of the subtitle file if it has the same name as the movie file, so in this example it wasn't necessary)

running mencoder

Let's say your video is 640 pixels wide and 272 pixels high (mplayer will tell you the dimensions, run:
mplayer mymovie.avi | grep VIDEO
).

We'd like to add a black border below the image to put the subtitles: for that we'll use the expand video filter.

Assuming your subtitles are in a file mymovie.srt, and your movie in mymovie.avi, now run:
mencoder -sub mymovie.srt -subpos 85 -vf expand=640:384 -ovc lavc -lavcopts vcodec=mpeg4:vbitrate=800:vhq -oac copy -o mymovie2.avi mymovie.avi

Some notes on the parameters:

• 85 is the percentage of the image height that the subtitles should appear (from the top)
• 800 is the video bitrate (in kbps), use higher numbers for higher quality video and larger file size, and vice versa
• obviously, if your video has a different height, you need to specify a different height in the expand=640:384 parameter