Q:

How best to power down an Arduino for ~5 minutes at a time?

Reading over the datasheet it appears the longest it can shutdown for is 8s so should I just keep a counter in the loop method that checks if it's run 38 times and then execute the code I want? Would this wakeup every 8s hurt battery life much if it's doing nothing but incrementing a counter?

A:

Yes, if you want to wake an ATMEGA (the chip in the Arduino) spontaneously (no outside trigger) from Power Down mode at periodic intervals, the you will need to rely on an interrupt generated by the watchdog timer, which has a maxim timeout of 8s. 
Your goal should be to wake, increment and check the timer, and get back to sleep as quickly as possible since the amount of time you are awake will dominate your average power usage while asleep. 
Some things to keep in mind...

The arduino uses a power regulator which always draws current. If you are going for long battery life, you will need to replace or eliminate this regulator. Much better to have an ATMEGA connected directly to a battery. 
Turn off as much of the chip as possible before going to sleep. Take a look at the power control registers. 
Make sure you are not driving any unnecessary loads with the GPIO pins when sleeping.

BTW, common wisdom has been that it is best to wake up and run at as fast a clock speed as possible to get your work done and get back to sleep as quickly as possible. However, Jack Ganssle recently published an article that makes a great case for doing the opposite. You will actually get longer battery life if you wake up to a slow clock speed, since this means you can run down the battery to lower voltage (this assumes you don'y need higher voltages for some other part of your circuit). Lots of other great info for designing long running battery-powered systems here...
http://www.ganssle.com/tem/tem275.html
Here is another relevant article about long running Arduinos...
http://www.openhomeautomation.net/arduino-battery/

