Basically, mix the dye in very hot water and put the object you want to dye into the dye bath. You cannot really mix the FRN base color and the dye color the way you'd think you might. I'd go for black. It will have about the same surface as before, so if it was shiney, it will be shiney; if it was matte, it will be matte.
You need to degrease the knife and clean everything out before you dye it or you'll get a very nice tie-dye effect. Great for lacrosse stix but not what you want for your knife, probably. And when you're through, you'll need to dry it out pretty well (though it's a Salt, so...) and then re-lube.
Black dye is pretty easy to find at fabric stores, some supermarkets, Walmart, etc.
Google up the RIT dye website and check their instructions. There's also a big threat at Spyderco forums on using RIT dye.
I've done it (orange D4 from a white FRN D4). It works well.