The maximum a 7805 can regulate is 1A, so you really want a bigger version like the 78S05 (2A) or the 78H05 (5A, not so common). And yes, you should have a heatsink on it, along with a tantalum capacitor and a reasonably sized electrolytic capacitor for nice smoothing and regulation.
Alternatively you could look for a regulated 5v supply, but they're not as common as a cheap unregulated unit.
Remember, when you're looking at a power supply looking to supply 1A, it's best to go way over that, say 2A to give a nice margin of safety.
