How should I power 3 motors (2 steppers and 1 servo) ? I guess the Arduino's power wouldn't be enough, and I need portable sources of energy anyway (as it's a robot).
FYI, I'll be using the Adafruit motor shield to control the motors and I'm using an arduino mega. (So yes, I'll need a battery for the mega too !)
Know any (easily) rechargeable batteries that could handle the Mega and the motors ? (not necessarily a battery that does both)
Hobbyking is good place to buy servos, (rechargeable) lipo-batteries and chargers. Quality of products can be difficult to know. Mostly it's ok, but can be poor.
You have to know needed voltage and current, after that it's easy to find battery. Leave some headroom above the specs.
I'm really new to electronics so I don't really know what kind of batteries are compatible and how much current / voltage I need !
Servos need 5 volts (6 V is possible too) and your stepper motors take 5 V too. Arduino works any voltage from 6 to 20, but 7-12 V is best choice.
You may change the higher voltage to 5 or 6 volt with part in next link, so called SBEC (UBEC makes (about) same thing).
By the way, fully charged 11.1v (Lipo-) battery voltage is some 12,6 V or even 12,7 volts.
You need to know both the peak current requirements of all your motors and the average current in normal use - the latter means you can estimate the battery capacity requirements for a given time of use.
Your battery will need to provide enough current (A) for the peaks and have enough capacity (Ah or mAh) to keep going for long enough.
If you have no exact figures how heavy load you will give to battery, you may just try some battery, like lipo you thought earlier (1000mAh 3S1P 25C). It can be ok, because your stepper motors are small and servo hardly needs much power.
Maybe you need (power cord) adapter for your country too. Or new cord. It is same type as in laptop comters, from "wall" to laptop power unit.
And how to use charger:
Always use "balance" charhing mode.
Next charger can make the job, but if you will buy bigger batterys, charging will take long time.