Someone mentioned waveforms. It's true it radically will alter it, but the point is that it uses psycho acoustic modelling to throw away what you are least likely to notice. These are based on:
A: Basic human hearing, you hear some frequency bands better than others.
B: Masking. Frequencies are masked by dearby louder ones.
C: Temporal masking
Now the models aren't perfect, for example mp3 splits your audio in to sub bands. The human ear can be modelled as a bunch of band filters of varying length. In mp3 the band filters used are of equal length to make things simpler so this is the sort of thing that can lead to discrepencies.
There's also a bit of irreversible maths that goes on which will cause some spectral distortion (I can't remember what it is exactly) so even if you had infinite bit mp3s you would still chagne the waveform.
So a very high bit rate mp3 should in theory sound good, but as the waveform has changed there's no guarantee how good it will be. If using a constant bit rate even at 320kb/s the mp3 encoder might run out of the bits it needs. So different recordings at different points have the potential to lose out. This will become more clear the higher end your equipment.
I think storing all music in mp3 would be a mistake because you may end up with higher end equipment that can reveal the difference, if you use any of the lossless formats you will always have a bit accurate representation. However listening to lossless files on your ipod is stupid as you'll quickly use up all your space. Worth noting that when this stuff was developed you couldn't go to pc world and pick up a 1TB hard disk!
It's the same for 16 bit music, after all cds are effectively lossy if you had an analogue recording, but if it's well made it will be mastered to make it sound as good as possible. You will get frequency distortion on a cd, whether or not you notice it is another matter.
There are better encodings than mp3 now but it will take a while for a true standard to emerge, lossless audio is very clever and mp3 is really only the first generation
.
So in short: yes they are different and you may or may not be able to tell. In theory you could end up with it sounding better, unlikely but the result afer the encoding coud potentially have altered the waveform for the better!