How many individual lights can an arduino control
I believe using Charlie-plexing N lines controls N*(N-1) LEDs. There is a good article on Wikipedia.
A friend of mine, Jimmie P. Rodgers, fit 126 LEDs on an Arduino Shield. He uses charlie-plexing to control the LEDs. Some information on his board is at -- jimmieprodgers.com/2009/12/my-development-process/ (archive.org copy)
At the last Boston Arduino User Group meeting Jimmie P. Rodgers drew a Charlie-plexing diagram as a matrix with labeled nets. Schematics drawn in this manner seemed to do a good job of communicating the concept. I created a couple of similar schematics -- See http://wiblocks.luciani.org/FAQ/faq-charlie-plex.html
You can use Shift Registers (http://en.wikipedia.org/wiki/Shift_register) to get as many parallel outputs from a single serial stream as you want.
You will need to be concerned with your power constraints. I have actually never used an Arduino myself but I am assuming it has a current limit just like PICs do. Also, shift registers will have a current limit themselves. If you run into this, you will need to look at using something like a MOSFET to allow you to control the LEDs without having to pull much power directly from your micro controller.
Any given AVR microcontroller pin is allowed to source up to 40 mA, and the total power supply sourced or sunk by the chip (i.e., at the ground and Vcc pins) needs to be below 200 mA.
Charlieplexing is a great solution for situations where you need lots of LEDs, but can get by with only one LED lit at a time. A standard Arduino board (like a Duemilanove) provides 17 "free" I/O pins, not counting TX, RX, Reset, or pin 13. So, you can hook up 17*16=272 LEDs. This can work well, especially if you're keeping one LED lit, or quickly scanning between just a few. But if you're trying to light the whole matrix with a pattern, you'll find that each is on (slightly less than) 1/272 of the time, so if your drive current were 30 mA at any given moment, each LED's average current would be about 0.1 mA-- pretty dim.
If you don't need that many LEDs but instead need more brightness, traditional multiplexing may be a better option. In this case, you use some of your lines as rows and some as columns in a matrix. If you use a 10 mA LED current, you could define a matrix of 4 columns and 13 rows, where all 4 LEDs in one row can be on at a time, and you scan through the rows. Then each row is on 1/13 of the time at 10 mA current, so the average LED current can be as high as 0.76 mA, BUT you only get 4*13=104 LEDs. (Definitely brighter per LED than with charlieplexing.)
The limit in the last example is the 40 mA per pin on the AVR-- since each row driving pin sources 4x10=40 mA. If you allow external transistors (which can be cheap and small) to be added to the row outputs, then you can avoid that particular limit and go brighter. For example, you could make an 8x9 array, with 8 rows and 9 columns, 72 LEDs altogether. One of the 8 rows is on at a time, selected through the transistor. Up to all 9 LEDs in a given row can be on at a time, driven at 20 mA, so 180 mA comes from the transistor, and you stay under the current limits of the AVR. The average current per LED is now 20 mA/8 = 2.5 mA-- usually reasonably bright.