Take what I say with a grain of salt.
What we're doing, basically, is applying an etchant (acid) to the steel in order to oxidize it until the reaction stops, then polishing off some of the oxides to allow us to get the reaction going again. We repeat this until we're satisfied with the results. You will need an etchant, a neutralizer for the etchant, and a polish.
What to etch with? Vinegar and ferric chloride (PCB etchant) both work. Rust remover works but is ugly. Dean tells us that bleach works but I haven't tried that. Acidic foods will do it as well. (The so-called food etch.) Each etchant will produce a somewhat different; additionally, any given etchant will work faster or slower and look better or worse depending on how diluted or concentrated it is. You'll have to experiment to find what you like best.
What to neutralize with? Something basic. Some folks use a bath of water and baking soda. I use spray-on glass cleaner from Wal-Mart with ammonia. Your call.
What to polish with? Never-Dull and Mother's both work for me. I've also used #2000 sandpaper. Different polishes (and polishing techniques) provide different results. Again, you'll have to experiment.
Now, how do we put it all together?
1. Degrease the blade thoroughly. Consider tapping or wrapping the handle and bolster with something to keep the etchant off. (I generally don't bother.) When you think that the blade has been completely degreased, degrease it again. Don't touch it afterwards.
2. Heat up the blade and the etchant. (I don't bother heating the etchant.) Use a heat gun, hair drier, whatever. I run it under the hottest water that my tap can produce until I feel the heat in the bolster and tang.
3. Apply the etchant. Dip the blade (if small) or paint it on. Cover the entire blade and keep the etchant moving or you'll get blotches. You'll see the blade darken, especially the hardened zone. Continue applying the etchant until the blade won't darken any further -- this is your signal that the reaction has stalled.
4. Rinse off the etchant and neutralize. This is not 100% necessary if you'll be doing more etch/polish cycles but it's good practice. It will also remove some of the crud. Use hot water to rinse as it will dry more quickly and reduce flash rust. If flash rust appears, don't worry about it.
5. Polish. Use whatever you use and follow the directions. Mind the edge. Don't overdo it. You want to get the worst of the oxides off but you don't want to polish everything off or you'll be back at square one with a mirror finish. Polish until nothing more is coming off.
6. Go back to step one if you're not satisfied with the results.
Generally, three cycles is the point at which the returns diminish greatly. I've gone as far as five or six with particularly stubborn pieces but it's almost never worth the added trouble. Sometimes I get lucky and the first etch does the job.
And now, the warnings, cautions, and notes:
-- PCB etchant is dangerous stuff. Cut it with three or four parts water. It will actually work better this way and will be far less hazardous. Diluted as such it will no longer burn your skin but it will turn it (and everything else, including porcelain) yellow. Don't swallow it and don't let it get in your eyes.
-- Hot vinegar does not smell nice. You have been warned.
-- Etching steel does not smell nice either. You have been warned again.
-- The edge remains sharp during the etch and since it can't be taped in this case, it's dangerous.
-- An oily fingerprint will mask the etch. If you want bright fingerprints on your etched blade, touch it after it's been degreased. Otherwise, don't.
-- Different steels react differently. Be prepared for surprises. There are two pieces in my collection which plain refuse to show a hamon after being polished, no matter what I do. It happens. Accept it.
-- Etchant on a brass bolster will discolor and possibly corrode it slightly. Mask it or be prepared to polish it afterwards.
-- Etchant on wood, horn, bone, antler, etc. is not a good idea. I've never damaged one like this yet but try to keep them clean.
I probably missed some things.
This is just my way to do it. There are many other ways to do it, some of which are probably better than mine. If you have a few hours to spare I suggest running some searches on "etchant" or such to get some other ideas about how to do this.