androidfanboy:
Do you mean the 10uF cap they show between RESET and GND or do you mean a decoupling cap between VCC and GND? I've never had any problem without using a cap for the VCC of the ATtiny.
A 0.1uf cap between Vcc and Ground. I absolutely have had problems on the ATTiny85 without this decoupling cap in place. Some would work, some wouldnt, some would start to program, but then die after committing the first page of flash... And everything was fixed when I put a 0.1uf cap across the top of the chip (these were the SMD ones). I guess that's why such misinformation persists - because sometimes, with some individual chips on some breadboards, it works (presumably getting by on stray capacitance in the system).