There are plenty of applications to convert video to various formats in Linux. One script that I ran into which makes the conversion so simple is Video2Avi. It is not a full fledges video converter because it can only convert video from other formats to AVI. Nonetheless, I find it quite useful because most of the video conversions I do is to AVI for my phone. It can convert VDs, ISOs, AVIs, MPEG, WMV etc. to AVI.
You can download the script from GNOME-Looks.org, extract it and double click on it to run it. It has a command line interface but using it is quite straight forward.
If you prefer to do it from the Terminal, download the script with the command
$ wget http://gnome-look.org/CONTENT/content-files/138805-Video2Avi.sh.tar.gz
Then extract it
$ tar -xzf 138805-Video2Avi.sh.tar.gz
After extracting, you can start using it right away.
$ ./Video2Avi.sh <path_to_video>
Replace <path_to_video> with the path to the video that you wish to convert.
Although you can already use it, you will have to add the path to the script everytime. This is rather annoying if you use the script regularly. So, copy the script to /usr/bin/.
$ sudo cp Video2Avi.sh /usr/bin/
After copying it in /usr/bin/, you can use it as
$ Video2Avi.sh <path_to_video>