Stainless won't darken like non-stainless does, in that it doesn't oxidize the same way by exposure to the air (oxygen). When 'carbon' (non-stainless) steel oxidizes, the iron reacts with oxygen to form iron oxide (Fe[sub]3[/sub]O[sub]4[/sub]), which is dark in color (almost black). With stainless, the added chromium in it will immediately oxidize instead, and it's essentially colorless or clear, with a very, very thin layer of chromium oxide on top of the steel. The chromium oxide layer essentially shields or prevents the underlying iron in stainless from oxidizing, which is what gives the steel it's 'stainless' properties. If the steel is scratched or abraded to remove the chrome oxide layer, the underlying chromium in the steel will again oxidize immediately, restoring the 'stainless' protection to the surface.
BTW, when 'red' rust forms on steel, it's due to the iron reacting to oxygen in the presence of water. The oxide formed by 'rusting' in such a manner is chemically different, with the formula Fe[sub]2[/sub]O[sub]3[/sub]. The added chromium in stainless steel will also protect against that type of oxide forming on the steel, by the same means.
Stainless steel can be 'discolored' by chemical etching with strong acids or other caustic agents, etching the steel at a microscopic level and usually giving it a flatter, greyer look. The greyer appearance is the result of microscopic pitting of the steel. It can sort of emulate the 'patina' on non-stainless steels, but it's not really happening the same way, at all. Many here like to use a strong etchant called 'ferric chloride' to etch, and therefore 'patina', stainless blades.
You're right, in that stainless steel (ALL steels, in fact) have carbon in them. The very definition of 'steel' is an alloy of iron + carbon. 'Stainless' steel is of the same composition, with additional chromium added to at least 12% by volume, which is what makes it 'stainless'. Non-stainless steels often have some chromium in them, but at much lower levels, often less than 1% of the alloy's volume. Some 'non-stainless' steels come very close to being stainless, such as D2, which has up to ~11.5% chromium in it. Technically, it's defined as a non-stainless steel, but it's close enough that it won't matter most of the time. It will 'patina' a little bit, but it happens much more slowly than in other non-stainless steels like 1095, CV, etc.
It's important to note that even 'stainless' steels can rust. As the name implies, it resists oxidation to make it 'stain less' than non-stainless steels; but it's not rust-proof.
David