There are several lossless formats.
For example: FLAC (the L stands for lossless)
To understand lossless you have to understand the mp3. Invented by Fraunhofer, it is an audio format which both vastly compresses the audio file and deletes some of it, but it uses human psychology to delete parts of the file that we hardly hear anyway. While it may be impossible to hear on a $150 stereo or a $25 pair of headphones, it can be heard with high-end stereos and headphones. Bit rate refers to the number of "slices" of music are lined up in a file. 64kilobytes per second loses a lot of the Mp3 and is audibly inferior to cd. 128kbps is near-cd quality... not that near and still audibly inferior, more noticeably if you listen to a short passage of music at lossless and then a short passage of 128kbps. You can double and double and double the constant bit rate, and you will eventually get to the point where you lose nothing from the original cd recording. That will be when you realize that your 5-minute song is over 250 megabytes. Then, only sixteen songs could fit on an Ipod mini.
The solution is to vary the bit rate, so that different bit rates are used for different sections of the songs, which gets in every last bit of data that was on the original recording. This is much more space-efficient than using a tremendous bit rate to code a recording... variable lossless files are only five times or so the size of regular songs encoded at 128kbps, which means a 5-min song would take up 20 megabytes, which would enable you to load a lot more songs to your player's hard drive.
I tried to make that as simple as possible... its the best i can do.
I use flac, and the best Mp3 player i know of which supports it is the Rio Karma, a 20gb hd player. I've heard the hard drive is buggy; im too scared to take mine on bike rides.