Parts: Replacement Engine Coolant Temperature (ECT) Sensor with O-ring gasket; part numbers are detailed below, according to your application.

Tools: NONE NEEDED

Estimated Time of Install: 3 - 5 minutes (10 if you're working turtle-slow)
Difficulty Level (on a scale from 1-10, 1 being easy as cake): 1.0 

If your coolant temperature gauge has become erratic, you most probably need a new coolant temp sensor. This means that instead of the needle going to the middle and staying there, like it should, it wavers all over the place between "Cold" and the middle. Get a new sensor and it'll fix the problem right up.

I'm writing this for the sake of people who actually SEARCH (hint: you should always search first) for answers to their questions/problems. When I searched, surprisingly I found that nowhere in the archives were there instructions on how to replace the engine coolant temp (ECT) sensor. I didn't even know where the sensor was until DigitalA4+ responded to a recent post of mine and also told me how to replace it. Before then, it was a myth that the coolant temp sensor is a PITA to replace yourself and you should let the dealer charge you $200+ to do it. All it will cost you is $25 for parts and about 3-5 mins of your time. Okay, so here's how to do it. Locate the sensor first. It's near the back of the engine, right in front of your battery. Depending on your model year, it may be black or blue. I have a 99.5, and it was blue on mine, thus very easy to spot. This is a pic of its location, though I already disconnected the sensor in this pic, at least it'll give you an idea of where it is (you can see the old and new sensors sitting up there, the metal clip, the O-rings, and the plastic U-shaped clips).

Now make sure when you buy the part, you have the correct part number for your application. The blue one is part # 078 919 501B, as the pic below shows.

 

Make sure to also get a new O-ring gasket when you get the ECT sensor. it's shown in this picture as the top-right part.

 

If you have a black ECT sensor, the part number is 058 919 501A (sorry, no pics of that one). I have heard that there is also a green sensor, part # 059 919 501A, but I'm totally not sure about that. Just pop your hood and check your model year's application before you go to the Audi Parts Dept.

Now, how to replace (remember, NO TOOLS NEEDED):
1) Remove metal clip holding connector, either by using fingers or using small pliers... I just used fingers cuz I'm lazy.
2) Unplug the connector
3) Pull out plastic clip from the outside of the tube (the top-left piece in the picture above)
4) Pull out ECT sensor and old O-ring gasket that's in the tube (the connector and tube are shown in this pic)



5) Put new O-ring into tube
6) Put new ECT sensor into O-ring somewhat firmly
7) Replace plastic clip around the tube
8) Plug connector back in
9) Replace metal clip

Voila, three minutes and you're done. I hope this answers people's questions about the coolant temperature sensor. As common a problem as this is for the A4 (it's VERY common), I was surprised to find little to no info about part numbers and how-to's. I write this tech article simply because the information available on this issue is so rare. Hopefully this helps people in the future. 
Disclaimer: This tech article is created for the purpose of benefiting Audi owners everywhere. I take no responsibility in any damage that may incur while attempting the steps in this tech article. As simple as this process is, please do at your own risk. Good luck and happy

Update

Update provided by Tom Cartmel

I have some additional information on the different colored sensors. The sensor installed in my car from the factory was black and stamped with a 'C' suffix on the part number. I contacted several parts departments at dealers, and they all told me that the black sensor is no longer available, and the correct replacement for the black sensor is the green sensor with the 'A' suffix. I can't believe that the dealer wanted to charge over $100 for replace this when I was able to do it quite easily with $5 in parts.