Duemilanove and the 'official' Arduinos in general are not designed with power management in mind, so to go lower than 10-17mA may require hacking it a bit or use of a nonstandard board. The big power drains on the Duemilanove are the USB-serial converter (powered all the time, even when a USB port is nowhere near), power LED and the CPU. You kind of need the CPU 
but the rest can go. Attaching a real-time clock like the DS1337 will let you put the CPU to sleep (<0.5uA) between measurements and wake it back up via an alarm interrupt. Without a way to tell it to wake up again, using the sleep modes in any meaningful way is tough. If you can't put a realtime clock / use sleep mode, if you can swap the (16? 20? MHz) crystal for a slower one, a software delay loop will use less power. IIRC you may be able to switch to the ATmega's internal oscillator via software control, not sure about this though. Either way, for timing-sensitive things like delay() and Serial to work correctly, you will have to edit boards.txt also to tell it the new speed you are using.
It seems like all my posts lately are spamming for my low-power Arduino project but these are pretty much the things I changed to make it work. Take the Duemilanove schematic (actually the Sanguino because I wanted more I/O), rip off that inefficient linear regulator and always-on LED, tie the USB-serial chip's power lines to the USB port rather than Vcc, and add a realtime clock. This gets it down to <1uA during sleep mode (including the realtime clock) and you can schedule the next wakeup anytime in 1-second increments.
If you can, using a "bare bones" board like the RBBB will get you most of the way there by getting rid of the USB-serial, LEDs and usually the big linear regulator. Feed it with a low-power regulator and a good-size battery (D cells, or 6V lantern battery if an automotive battery is too big), and it should go for quite a while.
Hope this helps!