One of the most important things is a full tang. The tang is an extension of the metal of the blade into the handle. In knives with a full tang, it goes all the way through the handle. This improves stability, control, and durability. Cheaper knives with partial tangs will have the handle break off over time.
In a chef's knife, you want a blade from 8 to 10 inches long, whichever is more comfortable.
You can also either get a forged or stamped blade. I suggest reading this article on the differences. To summarize, forged blades are softer, easier to sharpen, heavier, and have a bolster. Stamped blades are sharper, harder to sharpen, lighter, and have a welded on a bolster if any. With current manufacturing processes forged is not necessarily better than stamped. You should make your own decisions. All crap knives are stamped, but not all stamped knives are crap.
This brings me to one of the most important points: It must feel good in your hand. Don't buy an expensive knife just because it's expensive, or you recognize the name. Go to a store that will let you use the knife, Williams-Sonoma is one that will do this. If you can, bring a carrot in your pocket and actually cut that in the store.
I'll do some research on steel quality and update this later.