MP3 question

I have a question about MP3 stuff. As I understand it, the files available on the internet are (aside from possibly being illegal) low in quality principally because of compression/lack of bits. That said, suppose I wanted to transfer standard redbook cd material or lp material to an MP3 format. Provided I had enough memory (in my MP3 stick or whatever my particular unit holds data on), could I record my stuff in MP3 format for playback on an MP3 machine while retaining fidelity? Or, is poor fidelity inherent in the format?

The reason I ask is because I want a portable playback system, and the portable cd seems so large and bulky compared to the impossibly small MP3 players. Also, if I can store music on packs of gum rather than disks, all the better.

So, what say you?

Judd