MP3 encoders are entwined in legal issues that are too complex to get into here. Recording your personal CDs to listen to the music you've already paid for appears reasonable.
The encoder of choice is call lame. The Debian package is available at http://hive.me.gu.edu.au/.
The issue with MP3 is that the MP3 codec is patented by Fraunhofer in Germany, and a license is required to use it. To address this a free audio format has been developed called Ogg Vorbis. There are many utilities that will rip CDs to Ogg Vorbis format.