There is a DC barrel socket on the Arduino (well the standard form Arduinos anyway), just plug your battery into that.
You will need about 7V or more, 12V is OK so use a 12v battery for now.
When you have something working you can measure currents with a meter then make more decisions about what to do.
But if this is to be a small and long-running gadget you will have to seriously look at the design.
As for recharging, from what? Solar is the only real option I think because if you have any other source you have power and don't need to recharge 