The process is a two step process:

First,
Install the required packages
$ sudo apt-get install libavcodec-unstripped-52

Second,
Use proper command line tools for the conversion
$ ffmpeg -i source.wav -acodec libmp3lame -ab 64k destination.mp3

Now although it looks simple, I wasted two hours trying out different tools lame, mencoder, etc and wrong options with ffmpeg. Unnecessary bheja fry!

Cheers