Arduino Pro Mini power

Hello all, I am planing to do a project where every component should be as small as possible. That's the reason, why I am using Arduino Pro Mini, but I would like to know, how to power it with as small as possible batteries?

Than you in advance!

Also, the board: http://arduino.cc/en/Main/ArduinoBoardProMini

What is more, I am thinking about coin cell batteries or etc.

What are you connecting to it, and how long does it need to run between battery recharging or replacement?
You might consider one of my little boards with fewer parts than a promini, like no regulator, and run it at 8 MHz from a 3.7V LiPo battery with MAX1811 for charge control of the battery.
Cross Roads Electronics , scroll down to the bottom