Stainless steel does not rust. It gets surface stains from free iron on the surface, if this condition continues, due to repeated exposure to salt water, it can pit the surface.
Stainless comes in three broad categories - -
300 Stainless - - 303, 304, 316 are the most common. Some older forms are called 18-8. This is what the flatware in your kitchen cabinet is made out of. Great corrosion resistance because of the amount of nickel and chromium, but it wont take a sharp edge to save its life. 320 is the most salt resistant of the lot, mostly used for lab hardware and pipes.
400 Stainless - - Hardenable stainless. Not case hardened, but full hard the whole way through (at least in something as thin as a dive knife). This will hold an edge, but not the sort of razor sharp edge we would expect. These grades are very prone to 'corrosion' and 'staining' especially when near salt water.
Precipitation Hardening Stainless - - things like 17-4PH and the like. Full hard the whole way through. Corrosion resistance like the 300 series. A little pricey for dive knives, if anyone has seen one let me know.
FredT was on the right track with the Coke trick. Stainless won't rust, but if there is any 'free' iron left on the surface that is where your staining comes from. The Acid eats away the iron and leaves behind a layer of chrome or nickel oxide. I normally use a 1:5 mixture of white vinegar and water. I have to try coke. What you are doing is called 'passivation'. There is a diferent 'pickling' mixture for every grade of stainless, do a google search but most of the mixtures will be hell on earth to brew up at home. Stick with Coke or vinegar.
You need to do this when you pull the knife out of the package, and then after every couple of dives. After you let it soak for ~30 minutes, rinse it thoroughly. Don't worry about the acid eating the knife, once the free iron is removed the process stops itself. You then want to coat the surface with silicone gel or jelly, this is your added insurance. You also need to be very diligent about rinsing your knife after every dive!!
You should also acid soak the knife after it is sharpened. It can pick up iron from the last thing you sharpened. Try not to take a wire wheel or grinding stone to your knife becuase you run the risk of really coating it with free iron (and it will stain in a heartbeat). If it has started to pit a Dremel with a cloth wheel and a little rubbing compound should bring back the shine, be prepared to invest an hour.
Be especially careful anywhere there is metal to metal contact on the knife (i.e. hilt to handguard). Even if they are the same grade of stainless there is slight diferences in the exact composition. When dissimilar metals touch underwater they are prone to galvanic corrosion, which is a form of rusting. Look for a stainless knife that is just a metal blade with a plastic handle and nothing else, this will eliminate this problem.
The long and short, if you want a pretty dive knife, mount it above the mantle when you pull it out of the box. If you want a workable stainless knife, be prepared for maintenance after every dive. Are you thinking that the $70 for a titanium knife isn't that much now???