Yes. A "standard" Arudino (uno, etc.) runs from 5V, but there's a voltage regulator. The recommendation is 7V or more into the regulator, but you can usually get-away with 6V.
The higher voltage your battery is, the farther-down you can discharge it. For example, a 12V battery can go down to 7V (and it would be normally be considered "dead' or nearly-dead) but the Arduino would still be running fine with 5V out of the regulator.
On the other hand, the Arduino has a linear regular. That means it's inefficient and wasting power. The more voltage you "'drop" across the regulator, the more energy you are wasting. With a 12V battery, you are dropping 7V across the regulator and the regulator is burning more energy (and draining more battery power) than your main 5V circuitry.
And if you are powering additional circuitry from the Arduino's regulator, it can overheat. The more voltage you drop across the regulator, and the more current you draw through it, the hotter it gets. That heat is a direct result of wasted energy...
An external switching-regulator is nearly 100% efficient, almost no energy is wasted, and you'd get more battery life. The efficiency means you can get more current out regulator than is coming out of the battery (at a lower voltage). i.e. More hours from your milliamp-hours...
- Capacity (mAh)?
If you know how much current you're drawing, the mAh rating will help you estimate battery life.
- Chemistry (lipo, MiMH, alkaline etc)?
Of course, you need to decide if you want rechargeable batteries. Then, it's an issue of the type of charger you want to use, battery size, weight, mAh capacity, cost, etc. I wouldn't choose based on the "chemistry", but there may be a certain chemistry that best meets your specs/requirements.