When doing desigining circuits that need to have low power draw, there's a couple things you want:
1) Go for the lowest voltage that you can use - 3.3V is standard, 1.8V is available in some of the Atmel's lineup. This will drop the required power tremendously because of CMOS's V^2/R power consumption, as well as possibly simplifying your power circuitry.
2) Optimize the power required for computation - there's a tradeoff in terms of clock frequency and time spent in "sleep" mode. If you can get the processor to spend 99% of it's time in sleep mode, you can cut the average power consumption by 1-2 orders of magnitude.
3) Figure out the interface - people use bare LCD panes and microcontrollers with built-in LCD drive when they need to get months/years of lifetime out of something. You probably don't want to go this far, but if you are going to use LEDs, be sure to get high-efficiency ones that are bright at <5mA.
4) NiMH and NiCD have pretty large self-discharge rates - they'll naturally lose a couple percent of their charge per day. If this is acceptable, the use them. Rechargable Lithium types are a bit better - I think it's a couple percent per month or something. Primary lithium cells have a stupidly long shelf-life and are used when you want something to run for years at a time...
James