I know there are many projects on this already, but I think mine is slightly different. I have made a few lights flash to music with a TIP31 transistor and I wanted to achieve a similar affect with a strand of lights. Ideally, I would like to complete the project with minimal hacking (my original idea was too have the circuit connected to a GFCI outlet, so the lights could be plugged in, and then could be used for something else after. Anyway, does anyway have any idea for this? I was assuming I would have to use a microcontroller but maybe I'm making it too complicated. I did do some research on controlling PWM with a arduino, but that seems overly complicated just to he a few different light levels. If anyone has any ideas, please let me know. Thanks!
OK if you were using a transistor for your first lights they were DC. Since your Christmas lights run on AC if you just want to flash them or turn them on and off it can be done really easily with SSRs. But there is a very different way of dimming them so PWM will not help 
It can be done tho by taking a zero-crossing signal and timing a triac at intervals on the sign wave it gets a little complicated if your new. It can also be done a way that is a little out of the norm and im sure someone wont like it but iv used it many times with stage shows and effect lighting with hooligan incandescent and of course Christmas and rope lights. And that is to put a bridge rectifier in the AC line and actually switch the DC voltage with a logic level MOSFET. just be careful that your MOSFET is good to a voltage higher than your using. As always i suggest opti-couplers and total galvanic separation power supplys for safety when working with high voltage.
When switching dc from the arduino dimming is as easy as telling it how bright to be 0-255
analogWrite(ledPin, brightValue); //where brightValue is a number between 0-255
I agree. Rectifying the AC simplifies the circuit and eliminates the need for a triac zero-crossing circuit. If you can get one already made then great but if not, switching the dc is straightforward, as already pointed out.
For your safety and your Arduino's safety (and to protect your connected audio system), you need to isolate the power line voltage. This can be done with a solid state relay (or a mechanical relay) or an opto-isolator.