What are these stains on my stainless steel pans?
It could be that metals in your tap water are plating out;  i.e. the more active iron in stainless steel is being replaced by a less active metal such as copper. Manganese also tends to precipitate, leaving stain, and these, in particular, are dark colored, but can be removed.

Have your tap water tested, either at a nearby school or with a commercial kit(s) that include copper, manganese and lead tests. If there is a high concentration of anions, you might want to install an ion-exchange water softener.