The type and size of a battery ultimately depend on what the end application will be; you have to size your battery based on what it will be running.
Since all we know right now is that you are going to run an Arduino, we can take that as a starting point.
First off, the Arduino for simple development can be powered off the USB port, which is 5 VDC @ 500 mA. The Arduino itself can be powered externally by between 5-12 VDC, and I would stick to a source that can supply at least 500 mA (but you can probably go lower, it just won't run as long before the battery dies).
If you plan on driving servos or other higher-current needing devices (relays, motors, really anything beyond an Arduino and a few LEDs), you are going to want a larger source of current with a voltage size to match what you are driving, depending on what it is. Since we don't know any specifics, I won't give you anything here; depending on the end application, you could be looking at anything from a small LiPoly 3 VDC battery with a booster to 5 VDC, to a large glass-mat lead-acid monster pushing hundreds of amps at 12 VDC, or larger.
Something to keep in mind: If you are on a budget, and don't expect to be carrying your project around much, for an external power source, a 6 VDC pack composed of 4 "D" alkaline cells works wonderfully; you can push an amp or two with those, and it is cheap to buy anywhere. A quad AA pack works almost as well (or two such packs wired in parallel for double the current capability).
If you must use rechargeables, NiCad, NiMH, and SLA are the "safest" for hobbyists (easier to build chargers and such, but as with anything you should keep an eye on it while charging - also, SLAs shouldn't be charged in a sealed enclosure; despite their name, they do still give off small amounts of hydrogen while charging); LiION and LiPoly give you a lot of current (and sometimes voltage) for their size and weight, but if you fail to use the right charger, you can have a pretty amazing fire/explosion on your hands very quickly (watch some of the YouTube videos out there). They can be fairly safe with a well engineering charging system, but even there you can see failures (remember the cell phones and laptops that burned people?).
Hope this helps...