Powering the Arduino

USB
When the Arduino is connected to a computer via USB cable it is also powered by the 5 V USB line.
Alternatively you can use a plain USB charger to power the Arduino from a wall socket.

Power adapter or battery
The recommended voltage range for powering the Arduino via the VIN terminal or the 2.5 mm plug is 7 to 12 volts. Voltages above 12 volts are not recommended because the 5 V voltage regulator on the board will have to burn the additional voltage and become too hot. If possible use a voltage close to 7 volts e.g. some power adapters allow to set a 7.5 V output.
For low power applications a 9 V battery will work fine. Small 12 V lead batteries will also work fine.

Bhodilabs VPack battery packs
A nice option to power the Arduino board with 5 V coming from a single AA battery is a Bhodilabs VPack battery pack. Connect this battery pack to the 5V and GND terminals of the Arduino board. If your current rquirements are below 100 mA this works well e.g. with the infrared remote applications in previous posts. If you need more current there are two-batteries-pack available.
An advantage of the Bhodilabs VPack battery pack is that a alkaline AA battery has at least three times the capacity of a typical 9 V battery (1700 mAh to 3000 mAh compared to 500 mAh) and that there's no loss because of unneccessary high supply voltage.