It goes without saying that you'd need a proper hat, and there are some models that can protect your face as well as your frontal lobes. Here are some less common options that can provide superior protection to your gentle facial features.
Yes, I know -- they look hilarious. From second-hand experience, they work wonders (a friend of mine that lives only 300 km south of the Polar circle has one, and he swears by it). This will keep almost your whole face warm, and will be especially helpful in windy weather.
For that extra special spec-ops look. Combine with wired headset and stern look for extra confusion. I wouldn't wear one in civilized company even if my life depends on it, but don't count it against me.
Disclaimer: The author will not be held liable if you get arrested for suspicious behaviour when following this advice.
Other means of protection
Yet more ideas that couldn't be placed in other categories.
Grow a beard
Might not be an option for you particularly, but in Scandinavia beards and all sorts of facial hair are common, and not only as a fashion statement. This works essentially as a non-detachable beard hat, with increased social acceptance.
If you already happen to have a scarf, then you could wrap it up to cover your chin and possibly your nose. Slightly better appearance as far as aesthetics go (definitely less curious looks than those fancy beard hat thingies), but you'll need to do this right the first time, as any major adjustments when you are out in the cold are simply not possible, or at least -- not preferable.
This was part of a bigger answer originally, but was split in two for better cohesion.