It almost sounds like an oxymoron to talk about removing stains from stainless steel, but the reality is that there are many grades of stainless steel and they are not all resistant to all stains. In fact, anything stuck to stainless steel for a long period of time will probably leave a mark. The stainless steel spoon in the photo above was left in bleach overnight and it is actually pitted. Food stains that are acidic in nature can also leave their mark on sinks and refrigerators.
At the store you can buy special products called Stainless Steel cleaners. Understand that these are not designed to remove stuff stuck on the surface but rather to clean off atmospheric grime, brighten up the surface and leave a protective polish. Use them after you clean off the gunk.
The best thing for removing anything stuck to stainless steel is to start with mild dish soap and a lot of soaking, to soften it up and simply wipe it off. If you must use an abrasive cleaner or pad, carefully note that there is a grain pattern in the steel from the factory. Carefully follow the grain as any abrasive action across the grain will show up much more -- no circular motions. Always rinse all cleaners off totally, so that they do not leave their own haze on the surface, with the exception of the Stainless Steel cleaners which should just be polished dry.