Using 9 lanterns each having 3 LEDs in them gives you a requirement of 27 PWM signals. So I would use 4 shift registers and a software PWM like this:-
http://www.elcojacobs.com/shiftpwm/
But you need to drive 3 or 4 LEDs per shift register output, given 20mA per LED that is 80mA per shift register output. That is too much so you will have to use each shift register to drive a transistor to drive the LEDs. Each LED colour must have it's own resistor.
The total current for the lamps will be 27 * 80 = 2.16 Amps so you will need a hefty supply to give you that.