Der ATmega 328 funktioniert mit Versorgungsspannungen von 1,8 bis 5 V vobei bei kleineren Versorgungspannungen mit der Taktfrequenz zurückgegangen werden muß.
Andere Bausteine funktionieren entweder mit 5V (TTL - Schaltungen) oder Spannungen ab 3V (Cmos 4000 serie) von 2,5 bis 3,6V oder von 3 bis 5V.
Genaue Daten erhälst Du aus den Datenblett des jeweiligen ICs.
Deswegen genügt im allgemeinen eine Batterie alleine nicht um den Arduino Zu versorgen; Du brauchst dazu auch einen Spannungsstabilisator als Längsregler (78xx serie) oder als Switching-Stabilisator.
Das hängt von Deinem Board ab. Beim Duemilanove kannst Du 7 bis 12V - Pluspol an den Vin Pin und Minuspol an Gnd - anschliessen.
Mein Handyakku hat nur eine Spannung von 3,7V, das dürfte mit an Sicherheit grenzender Wahrscheinlichkeit nicht reichen.
Es gibt ein fertiges Lithium Backpack Shield, die einfachere und günstigere Methode (läuft bei mir einwandfrei) wären z.B. 6 Mignon/AA NiMh Akkus in einem Batteriehalter.