Stainless Steel Pan -- gray bottom. Why?
bikeboy definitely has it right, but just to be a little more specific:

What you're seeing is scale, also referred to as fouling and several other terms.  In all probability, it is specifically limescale that you're seeing, and it's very common in hot water taps, kettles, and on air-dried cookware.

If you have hard water (or even if you don't) it will tend to contain small amounts of dissolved calcium bicarbonate, which is completely harmless by the way, but when you boil the water it breaks down into calcium carbonate, which is still harmless but has low solubility in water and precipitates out into solid salts at lower temperatures.

This can also get mixed up with other salts you use in cooking to create more scale.

As you've noticed, soap and detergent do not remove the scale.  Nor would you expect them to; those things are intended for the extraction of oils and grease (and sometimes killing bacteria), and the above salts are even less soluble in oil than they are in water.

Acids such as vinegar or Barkeeper's Friend work because the acidity helps to dissolve those salts.

Bottom line, the mineral build-up is normal and harmless (to both you and your cookware).

If you want to prevent the build-up in the future:


Try not to use more heat than necessary in your cooking (high heats speed up the mineral breakdown).  Simmer, don't boil.
Always thoroughly dry your stainless steel cookware instead of letting it air-dry.  You'll wipe off the salts instead of letting them bond to the metal.
Rinse with a dilute vinegar solution after washing.


If you need to clean the build-up, use Barkeeper's Friend (which is what All Clad recommends using) or a boil some concentrated vinegar as bikeboy says.  Don't just use any old stainless steel cleaner, as not all of them are safe for cookware.