One of the cheaper and simpler yet still capable microcontrollers to get up and running is an Atmega328p on a breadboard.
The chip itself will run you about $3 in single quantities. It needs no crystal if you run it at 8 MHz on the built-in resonator. If you want to run at 16 MHz (or 20 MHz) then you need a crystal and two capacitors, for less than $1 extra. Add a 0.1 uF de-coupling capacitor for good measure, although that, too, might be optional in a low-cost scenario.
If you don't have clean 5V already, add your choice of voltage regulator.
To program it, you'll need a 2x3 pin 100mil header, and an external AVR ICSP programmer. The programmers can be found for $10 and up, and can be re-used for all AVR based microcontrollers. The program to use is "avrdude" (although you could also use Atmel's AVR Studio, if you're on Windows.)