Barkeeper's Friend can sometimes seem a little like magic. I've had what I thought were bad stains on my cookware, and that product always gets it clean.

My regular cleaning process is merely water and dish soap, but every once and a while I break out the Barkeeper's Friend and my stainless steel pots and pans look like new.