I really wish they were something you could pick up at Radio Shack, or even Jameco (although they do carry the ATTiny2313, but that’s a 20-pin chip, and way overkill for your project) but the normal place to get an ATTiny is Digikey.com (although it would be GREAT if Pololu would stock such items…).
Atmel has a free development environment, AVRStudio (latest release), which lets you write and download assembly-language programs to your AVR controller. If you also install WinAVR from Sourceforge, you can write C programs for the AVR, either in your their supplied editor, or from within AVRStudio (my favorite).
You’ll also need a programmer. Now, you can save a little money by building your own programmer, or adapting an evaluation board like the AVR Butterfly for programming, but I would recommend just buying a programmer, it’s a good one-time investment. The standard is the AVRISP-MKII, currently $36 from Digikey, but Pololu just came out with their own USB AVR programmer for $28, and some other nice features like direct access to the USB to Serial converter chip (which you probably don’t need to worry about).
You would need a clean 5V for the microcontroller and servo, probably from a voltage regulator, and at least a pull-up resistor for the reset pin. A power few capacitors and a second regulator would be good to keep the power constant and the motor noise form interfering with the ATTiny, but with such a small servo doing such light duty work it might not even be a problem.
You would want one of the controllers with a 16 bit timer/counter (I don’t think any of the 8 pin packages have 16 bit timer/counters, but if space is that much of an issue you could fake something with an 8 bit counter and more code). The 14-pin ATTiny84 (or 44 or 24, equivalent hardware with less program space, usually not worth saving the pennies only to run out of memory!) would be a good choice in any case. It could do servo control signals, or generate a higher frequency PWM output to speed-control a DC motor on command through a power transistor or FET.
Anyway, now you have way too much information.
-Adam