nemalk, your understanding of the basic options is correct.
However I agree with PaulS, if you are going to go with a battery you should use something with a higher maximum charge than a alkaline 9V battery. This charge capacity is measured in ampere-hours (often abreviated Ah), with smaller batteries it's usually expressed as milliapere-hours (mAh). A battery rated at 1 Ah can provide a current of 1 A for one hour. Here's a link
to an alkaline battery datasheet from Rayovac (note: the exact specs will vary depending on the manufacturer, but batteries of the same type and chemistry will have similar performance). As you can see although the 9V battery has a higher nominal voltage than one AA, it has approximately a third of the charge (~600 mA vs. ~1800 mA). Since the battery would not only be powering the pump when it's on, but also the arduino continuously, my advice would be to use six AA batteries connected in series (or even six C or D sized as they are all nominally 1.5 VDC
Battery holders for six AA batteris are readily available online, and might be in stock at a local hobby or hardware store. The majority of them will be designed to have all the batteries connected in series, but you'll probably want to make sure before you buy.