Say you have N arduino pins that you can use as digital outputs. (N is up to 19 on a duemilanove, since you can reuse the analog inputs as digital outputs if you really want to. A more realistic number is probably 11 pins, using only digital 2-13 (leaving 0/1 free so as not to interfere with upload and communications)
Assuming that you want "individual control" of each LED, and keeping in mind that at some point you also have to worry about exceeding the maximum current and/or power that the arduino can provide...
Connecting LEDs directly allows N LEDs to be used.
Using "multiplexing", you can have up to (N/2)2 LEDs. (actually, up to X*Y LEDs, where X+Y=N; 30 LEDs for 11 pins) Multiplexing is a technique where you connect the LEDs in rows and columns, with a pin for each row and column, and then light one row or column at a time, going through all of them too fast for the eye to detect flickering.
Using "charlieplexing", you can have up to (N*(N-1)) LEDs. (110 leds on 11 pins.) Charlieplexing is like multiplexing, but utilizes the "off" state possible with most microcontrollers so that the same pins can be connected to both a row and a column.
"LED multiplexing" and "charlieplexing" are both fine web search phrases that will turn up lots of information, explanations, tutorials, and even complete projects.
Using various forms of external hardware expansion, you can control essentially any number of LEDs, limited mainly by the communications speed with that external hardware, and the size and complexity of the program and data you need to control it. Peggy 2 is an example of essentially arduino-like hardware controlling 625 LEDs. (at some point, the external hardware exceeds the cost and complexity of the arduino itself, of course.)
Note that multi-color LEDs actually contain multiple LED chips internally, so that an RGB LED (for example) actually "counts" as three separate LEDs...