I remember those grapefruit patina knives you did, they were pretty cool.
Basically anything with some acid in it will patina the steel. Acetic acid and citric acid are probably the most common and safe to use.
Rolf, try rusting it with an acid, allow it to get a velvet coating of red rust(high humidity and temp, like in the bathroom with the shower running), card it off with fine steel wool then boil in distilled water. Repeat several times. This is a very old method, gives that very deep blue/black look.
-X