To dim lamps using PWM, you need the triac to switch on and off part way through the sine wave... Most SSR's are designed not to do this--they switch one and off at the zero crossing, since switching on and off during the posiitve or negative rise of the wave generates scads of noise. There isn't a really easy way to do what you want to do... See Light dimmer circuits link for an explanation of how dimmers work.
If I were goign to attempt it, I would try using an existing commercial dimmer pack with an analog control signal input, and send it a voltage to dim the lights.
Another option would be to hack an existing domestic dimmer, and replace the variable compoenent with an optically isolated resistor or something like that. Here is a link to an infrared-controlled dimmer.. the Arduino could send control codes via infrared, which is a great idea, since the Arduino and the AC are separated. http://store.qkits.com/moreinfo.cfm/K6712
Options that aren't optically isolated are very messy, as you run the chance of the AC feeding back into your Arduino, with ensuing kaboom! There really isn't a cheap and fast solution to this, unfortunately. Maybe someone else has the quick and dirty solution?
Here are some commercial solutions, fwiw. Note the big inductors, to reduce noise.
http://www.pwrseries.com/brochure/dim.htm
Solid State Dimmer Module here: Blue Point Engineering Inc. - Control Device Product - Add on's