I don’t use Gnome or KDE, so I didn’t bother with any of those fancy GUI multimedia apps. It’s just as easy from the command-line with abcde (A Better CD Encoder):
$ sudo aptitude install abcde id3v2 lame
$ abcde -o mp3
[wait, watch cute ASCII progress bars]
It doesn’t format the filenames in the particular way I like, but that’s configurable with a shell function you can define in ~/abcde.conf. Since this was a one-off, I just used mved to clean things up manually.
[Edit, 2011-09-03: My abcde.conf specifies a mungeheader() that works pretty well for me.]