Grip is a great CD ripper/encoder for GNU/Linux. If you have never tried it, give it a go. It rips to wave using cdparanoia or others. It can simultaneously encode the ripped tracks to the format of your choice. Supports cddb too. Easy to use.
I usually encode to the ogg vorbis format (...)
Ogg Vorbis is much better than MP3 (roughly the same audio quality for half the file size) and is free of patents.
On Windows, Winamp has always been able to play ogg files. If you don’t like Winamp there is plenty of other options too – ogg vorbis really is the successor to MP3.