How do I do that?
You need to monitor the line frequency, this is sometimes referred to as a zero-cross detector, it's easier to detect zero than it is to detect a peak or somewhere in between.
I would use a H11AA1 connected to the secondary of a transformer. The H11AA1 output will turn on when the AC is at/near zero volts and basically be off at all other points. So, there's the freq reference.
I would use the Arduino hardware interrupt to detect the rising/falling (as req'd) of the reference.
Then I would pulse the SSR on immediately for maximum brightness or later into the alternation (no later than 8msec, assuming 60Hz) for dimming (the later, the dimmer.)
Each cycle has 2 alternations, so there must be two triggering events per cycle (for full wave control.)
Once triggered the output will stay in conduction through the remainder of the alternation.
You can probably find more information on this in Arduino Playground.
<><> There's always
X10, pretty safe stuff, very effective.