Transformers are the easiest, you can salvage them from old hardware or buy them quite easily you want one with 120v primary and 12v secondary.
You can connect like this to a bridge rectifier and a capacitor:
http://www.bottleshare.us/dear-lyndon/
This will give you approximatly 12v DC, you will then need a regulator. The 78xx linear regulators are good and I have used them for years, however they are not that efficent and they generate quite allot of heat at higher loads. If you are only powering the arduino and a few other small components the 7809 would give you 9v that you cold feed into the arduino Vin, the arduino would then use its own internal regulator to get its 5v.
You could instead use a 7805 and connect this to the 5v pin on on the arduino and leave Vin disconnected, if the 7805 is attached to a heatsink you can take upto 1A from it.
What I tend to do is use small DC-DC converter modules like this:
http://sumaoutlet.com/new-lm2596-dcdc-converter-buck-dc-circuit-board-p-2755.html?zenid=68me4n1qdi20sqkp08u0shlq43
I adjust them to 5v and connect directly to the 5v pin on the arduino, these can give you as much as 3A and have a very wide input voltage.
I have managed to buy these boards from "direct from china type online stores" for about £1.50 each. If you need higher loads these are far more efficent than the linear regulators.
I am guessing for your application, you could select an appropriet transformer, rectifer(could just be 4 diodes), and capacitor and connect the supply to the Vin pin this will make use of the on board linear regulator.