Arduino by itself has 6 hardware PWM-pins, but PWM can be done in software as well.http://www.arduino.cc/playground/Main/PWMallPins
shows an example capable of PWM-ing all output pins of the arduino.
Needing at least 27 pins to control the shift-PWM library of Elco Jacobs, http://www.elcojacobs.com/shiftpwm/
, also done in software may be interesting as well.
Apparently Elco succeeded to PWM up to 768 leds (256 RGB leds) by software using 96 standard 74*595 shiftregisters. Using so many... there are a few ifs/buts, maximum brightnesscontroll has to be set to 32 instead of 255 like analogWrite() for example, arduino hasn't got the speed to PWM all leds in a finer resolution.
Up to 32 RGB-leds (96 pins/12 shiftregisters) brightness resolution can be 0-255 though and an 74hc595 doesn't have to cost much more as $0.25-0.45.