If you want to make your Arduino (or Arduino compatible) rig run for a good amount of time on batteries, you’re going to have to start optimizing your power usage. Marco has a good start on the subject. He’s using a library called JeeLib made by the guys who make the JeeNode (which oddly enough is very well suited for this type of activity or wireless sensors).
The tutorial gets you started thinking about your peripheral consumption (like those LEDs) and then finally working on the main CPU itself. Using the JeeLib library gives you an easy way to put your Arduino asleep for a while and wake up later to do whatever it is you need to do, or wake up based on some event.
While not very highly technical, it’s good to start getting in the mindset of power consumption when you are building battery-powered devices. Check out the article.