Here's a post I made in another thread about this. A lot of people seemed to like it, so I saved it for times like these.
Basically, when you encode a file you're looking at a tradeoff between size and quality.
When you make an mp3 (or mpc, wma, etc), there are two steps. The first is the rip, the second is the encode/compress. Ripping is basically just taking the data on the CD and converting it to a wav file. These are the best quality as they are bit for bit a perfect duplicate of the data that's on the CD. The problem is, they're big. Typically you're looking at around 10MB for 1 minute of audio. For a 30-40 minute CD, you're looking at 300-400 MB of space used up. So obviously that's not too good. So that's where encoding/compressing comes in.
You basically have a choice with what to do with the wav files. You can either encode it using a "lossy" compression technique, or compress it with a "lossless" audio compressor. Lossy means that some data is actually thrown away to make the file smaller. The data that is thrown away is typically sound in the ranges that humans can't typically hear at all, or hear very well. The idea is that you can lose some of the data and still sound fairly close to the original CD. Lossless means that no data is discarded. The resulting file is still a bit for bit perfect copy of the CD. But they result in file sizes that aren't as small as the lossy encoders.
MP3 & WMA are lossy. But even there, there's degrees of "lossiness". An mp3 encoded at 64kbps is going to be half the size of an mp3 enocded at 128kbps, but it's not going to sound as good. Mp3's typically are around 1MB per minute. But again, that depends on the bitrate they were enocded at.
The bitrate is basically how many bits are used to encode each second of the file. So a 128kbps file uses 128 kilobits per second. So it's capable of reproducing a sound that's closer to the original than a file that is only using 64 kilobits per second. So let's say we have a 5 minute 128kbps song. That's 300 seconds. 300 * 128 = 38400 bits. Since there are 8 bits in a byte, then 38400 / 8 = 4800 bytes or a little over 4.5 MB. The same song in 64kbps would be 300 * 64 = 19200 / 8 = 2400 bytes or a little less than 2.5 MB.
WMA claims to sound just as good as MP3 but at half the bitrate. So a 64kbps WMA file supposedly sounds just as good as a 128kbps MP3, but I personally don't think that's true.
APE is a lossless compressor. For me, it tends to average around half the size of a wav file. So if a track on a CD ripped out to a 40MB wav file, then it'll wind up somewhere around 20MB as an APE file. It's still not the easiest thing to store when you have a lot of CD's to rip, but they are a perfect copy of the original, whereas MP3's and WMA's lose quality.
Which one should you use? That's entirely up to you. It depends on how high quality is compared to space restrictions on your list of priorities. One thing to keep in mind though, that once you encode to a lossy format, there's no getting that lost data back. So if you encode everything as 128kbps MP3's and then you decide you want to use 64kbps MP3's on your handheld player, you have to convert from that file that's already lost data.
So rather than creating a 64kbps mp3 from the original best-quality CD, you're creating a 64kbps already lost a lot of quality mp3. And the results aren't that good. They might be satisfactory, though.
As for which formats work for which players, it's hard to say. Currently, I think the only supported formats are mp3 and wma. But a lot of players are what they call "flash upgradeable" which means you can later download an update that upgrades the player so it can support other formats. With the price of portable flash media, I doubt we'll see any players supporting APE, but they may someday support some of the other lossy formats.
The good thing about APE though, is that, since it's a perfect copy of the CD, you can convert it down to whatever bitrate mp3 or wma you want, and it'll be the same as if you originally ripped the CD to those bitrates/formats instead of from an already crappy mp3 like I mentioned above.
Hope this answers some of your questions, and I hope it's not too "techie". Feel free to ask questions though. That's why this place is so great.