I'm currently working on a small robot with 2 hacked miniservos, attiny45 and some photoresistors. I want the robot to be really small (it's about 6x5cm, 3-4cm tall) so am looking for a power source, that would be both small and efficient. I was thinking about button batteries but it turns out that they can only supply 0.1mA of continous drain.
A small Lithium Polymer battery would be the best choice from an energy density point of view. There are some quite small LiPo cells available from hobby stores, or alternatively you could use a cellphone battery, some of which are really thin and tiny.
Another option is to use some supercapacitors, but you wouldn’t get the same run time as you would from a LiPo.
As telefox mentioned, lipos are a top choice. They come in small packages and pack a punch. I have some rc planes(parkzone micros) with micro servos(actually should just be called micro motors) and such that use a battery no larger than 1.5cmx3-4cm running at 3.7v@100-200 ma. With components similar to the ones you find on these planes, you should be able to do a lot with the small size. Also sparkfun has a nice selection of lipos