Hi,
Most people do it using triacs. A triac is like two diodes in anti-parallel (in parallel, but with their polarity reversed) with a trigger pin. A triac conducts current in either direction only when it's triggered. Once triggered, it acts as a regular diode, it continues to conduct until the current drops bellow its threshold.
You can see it as a bi-directional switch on a AC line and can vary the mean current by triggering it in different moments relative to the moment the AC sine-wave crosses zero.
Roughly, it works like this: At the AC sine-wave zero, your diodes turn off and your lamp doesn't get any power. If you trigger the diodes, say, halfway through the sine's swing, you lamp will get half the normal current it would get, so it lights with half of it's power, until the sine-wave crosses zero again. At this point you start over.
If you trigger the triac sooner, your lamp will get current for a longer time interval, glowing brighter. If you trigger your triac latter, your lamp glows fainter.
The same applies to any AC load.
It is almost the same principle of PWM for DC. You turn your current source on and off quicker than your load can react, The amount of time it is turned on is proportional to the current your load will receive.
How do you do that with your arduino?
In simple terms you must first find the zero-crossing of the mains, then you set up a timer/delay and at its end you trigger the triac.
To detect the zero-crossing one normally uses an optocoupler. You connect the led side of the coupler with the mains and the transistor side with the interrupt pin of your arduino.
You can connect your arduino IO pins directly to the triacs' triggers, bu I would use another optocoupler just to be on the safe side.
When the sine-wave approaches zero, you get a pulse on your interrupt pin.
At this interrupt you set up a timer. the longer the timer, the less power your load will get. You also reset your triacs' pins state.
At this timers' interrupt you set your IO pins to trigger the triacs.
Of course you must understand a little about the hardware side so you don't fry your board, and burn your house,
And it goes without saying you must be careful not to kill yourself when dealing with mains AC =).
HERE is the project that got me started some time ago.
It uses AVRs so it should be easy to adapt to an arduino.
It is also quite complete, with schematics.
Their software is a bit on the complex side, so you should start with something simpler.