Ni Nardz. Yes, they will convert.
mencoder is a tool that comes with mplayer. It is a complex tool with many options so I cannot really say 'just run this'. Have a look at the docs, decide your codecs and then experiment.
Here is the beginning of the mencoder docs:
http://www.mplayerhq.hu/DOCS/HTML/en/mencoder.html
Here is ffmpeg docs, if you want to try that rather:
http://ffmpeg.mplayerhq.hu/ffmpeg-doc.html
To tell the truth, ffmpeg may be easier to try...