There is a writeup here on how light dimmers work:http://www.epanorama.net/documents/lights/lightdimmer.html
trying to summarise - you control the brightness by controlling the amount of the AC cycle that is allowed through to the bulb.
If you want an Arduino to do this (and it is possible, if not trivial), you will need to synchronise the Arduino code to the mains cycles (remembering that 50/60 Hz is no exact and can change up to 10% and any given time).
You contrl the brightness using a triac or thyristor. This would most safely be done using opto isolators.
As an alternative to dimming mains lights, there are a bunch of bright LEDs around which can be more safely controlled without using mains. Here is a link to a project that might give some ideas:http://www.electronicsweekly.com/blogs/gadget-freak/2008/02/pete-decided-to-give-his-lamp.html#more