I've dumped almost everything I know on the subject so I may not be much help. But I'll try...
[Pololu Programmer]
Looks good. Excuse me for being a bit noobish, but where does the other end of that cable plug into?
If you have one of the following from Evil Science, there's a place on the board for the 6-pin connector.
http://evilmadscience.com/tinykitlist/74-atmegaxx8
In my case, I mostly followed the instructions below with three exceptions: 1. Mine is powered either from a MintyBoost to get 5V or directly from 2-AA batteries; 2. I don't have a serial connection of any kind; 3. I don't have that clever little "AVR Programming Adapter" so I stuck six wires directly into the 6-pin female connector and then stuck the other ends into the appropriate holes on the breadboard.
http://www.arduino.cc/en/Main/Standalone
These were also very helpful...
http://www.ladyada.net/learn/avr/index.html
http://www.engbedded.com/fusecalc/
http://www.pololu.com/docs/0J36/all#1
http://www.evilmadscientist.com/article.php/avrtargetboards
I'm guessing I would I need a breakout board for the ATmega to connect the cable to the right pins?
That would certainly save some time and reduce the annoyance but it is not required. The whole thing can be built on a breadboard.
Would I need something like http://www.sparkfun.com/commerce/product_info.php?products_id=29
It looks like that one has the 10-pin connector. You will not be able to directly connect the 6-pin programmer to that board. I've read that a 6-pin to 10-pin adapter is easy to make.
Well, it will be run off of a regulated 2v power source on a device that gets its power from 2 AA batteries. I'll need to drive 4 leds, and that's about it.
It also depends on what the application does. I remember reading a proof on the AVR-Freaks forum where running a faster clock can, for certain applications, consume less overall power. It's important to remember than halving the clock means it will take twice as long to do a given amount of work.
I'm guessing the 5.5v is when it's run at 20MHz
Those two limits aren't related. In the datasheet, look under "28.3 Speed Grades". For the 168P, 20MHz is available at 4.5V.
Page 370, Figure 29-94. I can run the ATmega 168 at 4MHz using 1.8v. Awesome
That figure is labeled "Figure 29-94. Active Supply Current vs. Frequency (1-20 MHz)". I think you're looking in the wrong place for Voltage vs Frequency.
The "28.3 Speed Grades" section does show 4MHz @ 1.8V but only for the 168PV processor (the "V" is important).
How would I drop the internal clock down to 4MHz? I would need to set CKDIV8 to CKDIV2 I think.
I don't think you can. It's my understanding that the internal clock options for the 168P are 8MHz, 1MHz, and 125KHz. CKDIV8 is a simple "switch". If it's turned on the clock is divided by 8. If it's turned off the clock runs as-is.