I used Amazon's mp3 store for the first time this evening by purchasing Depeche Mode's song Precious.
Purchasing an mp3 from Amazon is like purchasing anything else from them. Precious was encoded with a bitrate of 256 kbps and a sample rate of 44,100 Hz. While it recommends their program for downloading (Windows and OS X only), it is not required, so things work just fine for those of us using Linux. I played it in Amarok and it sounds great. I highly recommend purchasing music from them.