What is the minimal set of parts for a circut with this AVR microcontroller?

All you need apart from the programmer and the chip is a couple of decoupling caps, and some way of connecting the programming signals to the breadboard.

So:

• 1 largish electrolytic cap (e.g. >100uF) You can maybe do without this if your source is nice and quiet (e.g. battery)
• 1 100nF ceramic across the power pins of the micro
• 1 10kΩ resistor to connect from the reset pin to Vcc to hold the micro out of reset.
• Some jumper wire to connect up nodes on your breadboard (you can buy ready made jumper wires, but I use a 22AWG roll and cut my own - much cheaper if you do this a lot)
• A header to plug your programmer cable into. According to the user guide it looks like you need a 2x3 pin 2.54mm pitch header.

Optional

• A button to connect your reset line to ground if you wish to physically reset the chip (I don't use AVRs, but I'm 99.9% certain the programmer can do this from the IDE)
• A crystal to use instead of the internal oscillator
• 2 * 22pF capacitors for the crystal (place from either side to ground)
• Passive components, LEDs, sensors, etc in order to do something useful with the code you write ;-)

Apart from the header (which is 10-pin with some unused pins - you can use the labels as a guide for your connections, the names are the same) this schematic is about the simplest I could find with a quick Google:

Funnily enough I just wrote a blog on doing pretty much the same thing with a PIC microcontroller (may be worth a look, the two are very similar)

I'm only posting this as an answer to hide the ugly URLs. You should certainly have a look at Atmel Appnote AVR042: AVR Hardware Design Considerations.