What I've found that works real well for cheap is the common cell phone charger wall modules. They are regulated switching regulators, quite small and light, and usually rated a +5.1vdc @ 1 amp. I find them all the time at thrift stores for 1-2 dollars. Just read the nameplate data carefully for actual voltage, current, and connector polarity. Then just wire it to the arduino's 5V and ground shield pins.
Lefty