First, practice playing with LEDs using the Arduino's digital pins (remember, you can use the analog pins with digitalWrite(), too); once you are comfortable with that, you can move on.
The next step would be to simulate a shift register using the Arduino's pins (the "why" will become apparent soon); put your logic for this simulation into a function; into this function you will pass an array (well, a pointer), of boolean values, and another argument indicating the length of the array.
Now - in that function, you're going to want to loop thru the array, and for the first N elements (let's say "8"), you set the digital pins (you might want to use a switch case here, or perhaps a second pin mapping array to do the element number to pin number conversion). Read the element, and if the value is FALSE, write a LOW to the pin, and if it is TRUE, write a HIGH to the pin. Advance to the next pin, repeat until you run out of pins.
Before you call the function, you set up the array to have the pattern of the lights you want to display; so you might want to write a bit of code in the loop() function to randomly set the pattern of bits in the array, then call your function, and repeat.
Now, why would I tell you to simulate a shift register? Basically, because it will give you a feel of how a real shift-register works, without you needing to understand hooking up such a device, keeping everything simple until you are ready to advance. By putting the code into a separate function, you can later swap the "black-box" innards out to new code to drive the shift register, without needing to change your main code (so, you could potentially develop everything you need on the Arduino in a fell swoop, then change a few variables for the larger number of lights, swap in the hardware and various code to work with the real shift register, and if anything is wrong that looks like a code issue, you can be fairly confident that it isn't in the main code, but instead in the custom function, cutting debugging time).
Once you have the "fakey" shift register working with the Arduino's pins, I would then try to move to hooking up a few real lights. Assuming you know what you are doing with household AC, go out and get the parts for the lights (sockets, wire, lugs, crimpers, electrical tape, etc), but only a few (maybe 2 or 3, depending on your budget). You are also going to want to purchase the same number of what are known as SSRs (solid state relays); these aren't cheap (cheaper if you go surplus, though), so be aware of that. But they will do the job you want to do, which is easily switch AC currents using TTL (transistor-transistor logic - 0/5VDC, generally) levels. The SSRs you buy should have an input for TTL level switching, and an output side to switch 110VAC; when you buy them, you will notice that they have a metal base, and holes for bolts - you are going to want to attach that base to a piece of metal, with heat-sink grease in between the mating surfaces; they can get warm during operation, and need a heatsink to continue operating properly. There will be screw lugs on both the input and output sides, one pair each (TTL signal and GND on the input side, and the two poles of the AC switch on the output side). Wire the output up like you would a switch for a lamp. Wire the input with the GND to the Arduino's GND, and the TTL signal to one of the digital pins.
After checking, double checking, and triple checking your wiring (you did check, right? CHECK IT AGAIN!), you should now be able to run your code, and for those few lamps connected, they should light up like the LEDs do, and turn off as well, just like the LEDs did before.
The next step would be to get a shift register (well, several, depending on how many lights you are hooking up, read the datasheets, but most are either 8 or 16 bits wide, for 8-16 lamps), and hook that up; basically, such a register works by a few lines (a DATA line, a CLOCK line, a LATCH line, and a GND line, along with a VDD line to power it), the data line, clock line, and latch lines are connected to digital pins on the Arduino - the GND connected to GND on the Arduino.
To send data to the register, you clock it in: bring the data line high or low (depending on if you want a 1 or 0, light on or off, respectively), then toggle the clock line (take it high then low - though some are inverted, see the datasheet); when all the bits are sent, toggle the LATCH line, which writes the data over to the parallel pins on the shift register - these pins are then connected to your LEDs or SSRs, whichever. Something to keep in mind about the toggling of lines and such is the timing; if the code runs too fast, the toggling may happen at the wrong time for the shift register to keep up, and you may not get what you expect; on the datasheet, there will be what is called a "timing diagram", showing simulated traces of high-low values for each line being toggled over time, with the number of fractional seconds needed to wait, etc in between so that your timing is correct.
How do you attach more lights if you only have a certain size shift register? Well if the register is designed for it (most all are), there will be an "overflow" or "data out" or "shift out" line - this is simply daisy chained into another shift register (there may also be a clock out line, or you just hook the clock to the "master" clock line you are running with the Arduino); when the data goes beyond the "length" of the register, it will feed over into the next one (basically, shift registers are nothing more than a bunch of flip-flops daisy-chained together).
I hope this helps you; I appologize for the length, but a lot of people ask how to do this, and I want to help set them on a good path toward implementing their project, while avoiding some dead ends.
Good luck!
