I used mencoder utility to convert my video files. But it was compiled without libfaac. So if you specify AAC encoding, an error occurs. Details and solutions can be found here. I just added the Medibuntu repository as described:

NOTE: ffmpeg utility in Lucid release does not support *.rm/*.rmvb yet.

Then install mencoder and codecs:

Now you can convert videos. Here’s a sample to convert a *.rmvb(848×480) to a *.mp4(320×240):

Modify fps/codec/bitrate values as you wish. The aglobal & vglobal options seem to be essential for iPod.

In order to keep video aspect after scaling, the output file should be 360×204. we use the -vf-add filter to add black band to the top and bottom of it. Other command line options, please refer to its manpage.

Lastly, install gtkpod to import your *.mp4 files.

Updated Mar 27, 2012: The above command line is for iPod Nano. For high quality H264 encoding used in iPod Touch or iPhone, run: