Thanks to this guy for cutting short my evening-long search for a way to rip CDs to MP3.
He's right, it is ridiculously hard on Linux. My understanding is that that's because That Can Get You Sued, and Canonical is probably big enough to be a tasty target for the MP3 patent holders.
Normally I would use the ogg format, but I just got a cheap mp3 player thingy and none of the cheap ones seem to handle ogg. I did check.