What sensor(s) to detect (frozen) steamed up mirros?
You could actually achieve this pretty simply with a reflectance sensor setup.  Essentially it is a light and a photodiode that detects the reflected light.  This kind of sensing solution is used on many line follower robots.

In your application, as snow, or freezing ice, accumulates on the window or transparent surface, the more blocking of light it will be.  So if you put a light behind the glass, turn it on, and then measure the amount of blocked or reflected light, you'll be able to tell how much snow is there.  You will have to do some tinkering to get your desired setting on when to turn it on will be but this is a good solution if you want to keep it out of the outdoors.

I think this could work with fog, although I can't say for sure right now. 

Sparkfun has two solutions, one with an analog output, and one with a digital output for relatively cheap and can both be used with a something as simple as an Arduino.

Edit: (New information added to question)
Since you're looking for a solution on your side mirrors and not your windshield, you could look into placing a similar solution used to detect rain onto the mirror.  It would essentially be a couple of wires, traces to be exact, that are not connected initially, although when water is frozen on the surface, the wires would be connected since they conduct electricity.  Sensing it would essentially be polling the wires, setting one as an output and the other as an input and toggling the output to see what you get on the input.  

There are a few videos on youtube and such explaining how to get circuits onto a surface such as glass, although I'm not sure how it would work for a mirror surface.  If you decide to go down this route, test it out on one a junky makeup mirror or something first.

To get an idea of how this solution works, check this out