How do you figure out an efficient battery setup for a project?
Our beloved admin Nick Gammon has made a very neat articile on this subject, I suggest you read it and apply as many of the methods he described.

Also, it can be worth to check the requirements of your project, how long should it work on battery to be acceptable? Set some realistic boundarys to avoid getting lost in (trying to) optimizing beyond all practical purposes.

There are two places where you can save power:

In software

The Atmega328P has a few tricks to save power.
Most notably is powering down peripheral devices and/or using sleep modes.
I believe the P version of the Atmega328 also has more power saving modes/ is more efficient overall.

Also take a look at this.

In hardware

An Arduino board has a lot of chips that may not even be neccesary on your battery project.
Most notably the USB interface chip, if you're going to run off battery, you most likely won't need this chip.
But also, the voltage regulator on the Arduino is, I believe, a linear regulator and is likely to be inefficient.
Also power/status LED's will some current.

You can choose to put a ATMega328P on a breadboard, and power it directly with a source that will be between the min/max voltage of the ATMega328P. This way you don't get the losses that a regulator will have.
If you want to use a regulator (for a higher voltage source) you should use a switching regulator, they're typically more efficient.

Mind that on low voltages, the ATMega328P can't do a 16Mhz, but it's actually a pretty interesting point, since it will consume less power on 8Mhz, or even less on 1Mhz.