My favorite patinas? Natural, well... semi natural. Basically just using the blade in the kitchen cutting up everything. Potatoes, onions, tomatoes, and fruit. This patina is awesome because its completely unpredictable and it forms slowly.
Another good one is to place the blade in a cup of almost boiling vinegar. It will put a nice even patina on the blade as long as the blade is free of oils. This can also be a "base" patina for further "patina-ing."
Soak a rag in vinegar and wrap the blade in it. The contours of the rag will pass onto the steel.
Almost any condiment will work, apply thinly, thickly, dab, spread, or draw. The patina will form on the outskirts of the condiment is. So typically thinner works better.
Onto something more sinister.... CHEMICALS!
Gun blue of course will blue the blade... its what its meant to do. Its fast, easy, and can be applied then the whole shabang placed in bleach for an acid etch. PERMANENT! (tons of info on this forum about this)
One I have played with is muriac acid. Stuff can be nasty so I wouldnt recommend this for everyone, and you need to dilute it properly for it to work right, or dont... either way it can be very aggressive.
Another is a cleaner called lemishine. Its basically citric acid crystals. You can dissolve it in hot water or make a paste. Once again its pretty aggressive yet safer than other acids. I've never heard of anyone else using this method. IE you can etch/patina stainless like aus8 or KAI's sandvik with it easily.
Once again when using chemicals use common sense, safety, and dont be silly. You dont want to end up looking like the Phantom of the Opera do yah?