I'm a big fan of ordinary high-carbon tool steels. O1 is my favorite, although good blades can be easily made from A2, 1095, and 5160 (the #1 steel for swords.) I also hear good things about Crucible CPM-3V.
Damn few stainless steels will even come close to the toughness and edgeholding of a good carbon steel blade. They stay shiny, though.
I've made a few knives from O1 (Starrett No. 496, if you care) and found it very easy to work and forgiving to heat treat. I heat treat my knives almost glass-hard along the edge (Rc 62) and draw the temper down towards the spine (around Rc 56-57.) This makes for a very tough knife that can handle a lot of prying, poking, and chopping, but which has an edge that gets scary sharp and stays this way a long time.
Short version - look for a knife made of a high-carbon steel (not a high-carbon stainless steel) and query the manufacturer about their heat-treat process.
- Chris