Headbands are a good idea! One that's very nice and can be worn alone to keep most of the head and the ears warm is Calorimetry; another good one is Quant, if you want to get adventurous and tackle entrelacs. (There's a good addendum to Quant online somewhere for making both ends match up better, if you want to search it out - alas, I can't remember where I got it from!)

Shawlettes (smaller, usually narrower, shawls) are good too - you can wear them as scarves or over the head and tied round the neck (if they're long enough).