I'm a lurker on two knife-related forums (Bladeforums.com and Knifeforums.com). On both of them, "what knife should I buy" or "what is the best knife for X" are either closed quickly or become very hot topics because there is no right answer, only lots and lots and lots of opinions. See this thread for a recent discussion of the topic (including some nice pictures).
That said, there are some general guidelines.
First of all, make sure it is legal! Carrying an illegal knife on the Appalachian Trail will get you in the same trouble as carrying an illegal knife on the streets of New York. A LEO might cut you some slack in the wilderness, but they don't have to.
Fixed blade vs folding blade.
Fixed blades are tougher, which is great if you are going to be splitting firewood or cutting branches or digging holes.
Bigger blades (both length and thickness) are better at chopping wood but are far worse at small tasks like skinning small game and slicing food and cutting rope.
Serrated blades are better at cutting fibrous materials like rope but suck at cutting soft food like cheese and tomatoes. Typical bushcraft tasks are usually better with a straight edge (though a serrated edge makes pretty good feather sticks for firelighting).
Harder steels hold an edge longer but are harder to sharpen in the field. Softer steels might roll over the edge when chopping.
Some types of steel are better than others at making sparks from your fire rod.
There is no such thing as rustproof. Stainless steel is just steel that takes a bit longer to rust. :-) All knives need good care. Unless you are spending a lot of money on a titanium blade.
Straight edge blades (like the "american tanto" design) suck at cutting food. The curve, or "belly", of the edge is what helps cutting through the entire draw of the knife.
Saws on the back of the blade mean you can't use the blade for batonning very well and you will hurt your hand in some knife grips. A lot of military knives with saw backs are for ripping through aircraft skin. Leave the sawblades to Rambo.
What do I carry?
I carry a Victorinox Outrider Swiss Army lockable folding knife. The long blade is for food prep (it is long enough to cut through an apple in one go). The sawblade on it is long enough to deal with firewood and track maintenance. The scissors probably get used more than anything else on the blade. I've used the can opener a few times and the corkscrew only once (wine bottles and tins don't go hiking often as they are heavy).
If I am going somewhere camping I also carry a CRKT Stiff KISS MDP. It is small, light, strong enough for me to whack it through wood with a baton and cheap enouygh that if I break it I don't care. It is a bushcraft knife and does not go near food.
The Victorinox is legal carry in New Zealand. The CRKT is not, so I have to make sure it stays in my backpack when driving to and from the trip.
You are not Rambo. Don't carry a massive piece of movie-madness cutlery (termed "tacticLOL" on the forums above).
If you are Rambo, then disregard all of this. You can do whatever the heck you want - I'm certainly not going to argue.
Edit: Thanks Ben.