Stainless steel gets its corrosion resistance from the addition of at least 10% by weight of chromium into the mix. Much like aluminum resists corrosion by forming a layer of aluminum oxide corrosion that then protects the bulk metal, the chromium forms an oxide layer that protects the steel. Some good general info on some details about stainless steels can be found on About.com, but it starts out with a myth about the discovery of stainless steel which you may have heard. The myth is that stainless steel was accidentally discovered in 1913 by British metallurgist Harry Brearly, when he noticed that some samples of an experimental alloy he was planning to throw away hadn’t rusted after sitting on a shelf for several months. In fact, Brearly knew what he was doing; it had been known since the 1800s that adding chromium to steel increased its corrosion resistance, and a number of inventors around the world had already developed materials that would be considered stainless steels today before 1913. (Source)
Unfortunately, stainless steel can and does rust. In seawater, for example, the plentiful chloride ions (salt is sodium chloride) can bond to the chromium and destroy this coating, causing the steel to rust, often called pit corrosion for the appearance it has. There are special marine grade stainless alloys that are more resistant to this because of other elements added to the mix. Additionally, since steel contains carbon, the chromium can bond with the carbon to form chromium carbides. Carbides can form when the steel is heated to high temperatures; for example, in the heat-affected-zone of a weld. The carbides tend to form along the grain boundaries of the material, so the corrosion follows the grain boundaries. Therefore, this phenomenon is called “intergranular corrosion.” In the specific case of welds, it is also called “sensitization” or “weld decay.” This form of corrosion can be minimized by using stainless steels with low carbon contents. These alloys are identified with the letter L: for example, 304L and 316L. Even if it doesn't rust, stainless on boats changes appearance with age in the marine environment, becoming darker, more gray, than it was when it was new.
The second most common myth is that stainless is non-magnetic. I actually have a few of those rare earth magnets in my shop and test my hardware with it, but I know it's not the final word. The two most common series of SS alloys are 300 and 400 series; the 300 series is either nonmagnetic or only slightly magnetic, while the 400 series is magnetic. My test is that if it's not attracted to those strong magnets (given the right appearance, etc.) it's definitely stainless. If it is attracted to it, it still might be stainless, and I might need to do something else with it.
You'll see the terms martensitic and austenitic to describe steels; these terms might be useful to materials weenies, but I find it easier to work with the number series of steels. 300 series alloys are austenitic while 400 series alloys are martensitic. Those terms have to do with the crystal structure. Martensite is formed by the rapid cooling of the alloy while austenite is formed by slower cooling. The crystals are completely different. Austenite is a "face centered cubic" crystal while Martensite is body-centered tetragonal (BCT) crystal. The cool thing about steels is how they can be customized for the properties you want by tweaking both the composition and heat treatment.
For my general shop use and hardware on boats, 316 stainless is what I tend to use and prefer. 303 is a "free-machining" stainless. Free machining stainless steels are created by the addition of a couple of percent of sulfur, which sacrifices some corrosion resistance. You'll find 303 used in lots of places including, surprisingly, jewelry. 400 series steels are stronger than 300 series, but the trade off is less corrosion resistance. 416 SS is a commonly used alloy, a strong alloy, but it's not going to hold up in harsh environments as well as 316. You'll also find references to other alloys, like "18-8". These aren't part of the formal 300 or 400 series, but are similar; 18 is the percent chromium and 8 the percent nickel. That particular alloy is closer to 304 than 316. Your search engine is your friend for questions like "18-8 vs 316".
Unfortunately, if you go and just buy "stainless screws" that don't specify the alloy, it can be hard to know what you're getting. Having a supplier you can get that information from is a big plus. Boat manufacturers pay extra for a guaranteed supply of 316 - even when they buy hardware by the drum. We might have to pay extra to get what we want, too.
A common problem with stainless hardware is galling; stainless bolts in stainless nuts can actually cold weld to each other and have to be cut apart. Galling can be reduced by using coarser threads or by a PTFE (Teflon) lubricant before assembly.