For me, feature number one is regulated light output. When I bought my first head lamp I was quite surprised that the brightness significantly dropped after a few initial hours. This is called unregulated light output: the brightness simply decreases as the battery level goes down. It means that you will only enjoy decent brightness for the first 20 % of time or so and then the light output falls below a decent level and gets progressively worse. Regulated lamp keeps the brightness at constant level and then stops working more or less suddenly at the end of the battery lifetime. Here’s a graph comparison taken from Princeton Tec:

I much prefer the regulated mode, to the point I don’t get why decent outdoor stuff manufacturers like Petzl still sell unregulated lamps at all.
Second most important thing would be the power source. I’m happy with a compact lamp that includes the batteries in the same box as the light source. Depending on your requirements you might need a separate battery box. It offers more power and you can keep it under your jacket in cold weather to keep the batteries warm and happy. On the other hand it’s another thing to keep somewhere on your body and another possible point of failure (the cables between the battery pack and the light are known to be pretty flimsy).
If you decide for a compact lamp where the batteries are in the same box as the light source, you still have the choice at least between AA, AAA and special batteries. I have a lamp that requires 3 AAA batteries and wouldn’t choose the same type again, because I can’t easily change batteries between my gear (the GPS and camera use regular AAs), the AAAs are little less common (so you might be out of luck when looking for cold-weather Lithium batteries, for example) and the odd number of batteries is a nuisance when charging. For similar reasons I don’t want a lamp powered by special batteries.
I mostly don’t care for other things. Waterproof body is always a good idea. And there’s always the question of how much light power is enough. The simple answer is any modern LED lamp will probably do for you, unless you have some extra requirements like fast movement (biking, skiing or running in the night). If you do have these extra requirements, it’s good to see what other people in your target group use, and test in the real conditions.