Just to add a few details:
With lossless the datastream is compressed in such a way that the original datastream can be recreated at playback. It is the result of the fact that almost all sequences of 0 and 1's can be stored more efficiently, without losing any information, just like zipping a computer file. As a consequence, indeed the compression rate varies, and random noise may even be more difficult to compress faithfully than real music. Different lossless formats differ in the way they try to find the optimal compression during encoding. The algorithim (eg for flac) may have a high setting so that it spends more time trying to look for the best possible compression and a low one that is fast but with less efficient compression. In practice the settings do not differ much, the low ones are already quite efficient. Most algorithms try the spend their computer time in the encoding phase (making the compressed file) and keep the decoding fast, so that playback is not limited by computing power on a (portable) system with a slow cpu.
Lossy compression is more interesting technically, as choices have to be made what information to keep and what can be ignored - not just informatics but also the human factor of real hearing sensations comes into play. Lots of different methods have been developed, but of course the higher the bitrate the higher the faithfullness. It is quite amazing that a reduction to 10-20 percent is possible without too much damage to the listener's appreciation. VBR helps because the algoritm can use more bits for complex music phrases and less for the simpler ones, resulting in a higher quality given an _average_ bit rate for a track. Downside is that at playback the cpu must be able to decode the complex sections without getting behind (which would result in a dropout). If storage space is not limiting there is no reason to resort to lossy compression.
Upsampling (by modern DACs) is in a way the reverse of lossy compression: an algothm is used to recalculate and reconstruct a hypothetical original higher quality datastream before it was reduced to the 44.1kHz/16bit. The latter is a lossy compression of the master recording that if I remember correctly usually uses a 96kHz/24 bits AD conversion. It involves intrapolation, but appears to make the postprocessing by analog filtering at playback easier/better.
Pete