The hd800 will sound much better than most other headphones even without an amp. However... 1) your volume will likely be very limited 2) they will improve GREATLY with an amp.
Mp3 is a big no no with the hd800, it'll sound unlistenable.
A cheap amp that will drive the hd800 is the lovely cube or m-stage matrix. Don't forget you'll also need a good DAC, I'd recommend the dacport lx if your looking for something affordable.
I mostly agree with this information. A decent amp with work just fine with the HD800 - though I've had solid results playing 320kbs mp3s on a iMac. I imagine it would be even better with a good DAC.