Let me jump in too, some philosophy, some how-to...
Stan's comments are right on the mark about attitude. I definitely am not a masochist, but I do confess to a warm, fuzzy--OK, smug--feeling when I'm out there and the other guys aren't. Some of my greatest runs have occurred, when by any objective standard, the weather stinks. In a certain sense, there's no such thing as bad weather, only weather for which you are unprepared.
Here in PA we get our share of cold weather, though not as severe as the upper Midwest. But regardless of the absolute temperature, we all know the standard advice is that you gotta go in layers. That's correct, but what you don't really hear emphasized much is the flip side--that you also gotta be willing to peel off those layers as you warm up and with temperature/wind changes. For example, in say 0-10 degree weather I wear a long sleeve polypro type turtleneck, another long sleeve T-shirt, and then a short sleeve T-shirt. If I sense that I'm sweating a little too much I'll stop to take off the second long sleeve T-shirt and tie it around my waist before my whole top gets real wet. Also I'm always tinkering with my knit hat, mittens, whether I push my sleeves up, etc. In other words, actively manage your personal microclimate. Sure, it's a minor hassle to peel clothes off/on. You can't avoid getting damp from sweat but you do want to avoid getting wet.
If the winds are strong, or if I'm going to be off the beaten track I'll also begin the run with a windbreaker top on, or around my waist for backup.
My wife worries about me going off into the hinterlands alone, and even though I always tell someone where I'm going and when I expect to be back, let's face it--if you keel over for any reason you're going to be out there hours until help arrives. You could freeze, literally. So in my belt pack I always carry a space blanket (virtually no weight) plus a candle/matches with which to start a fire (assuming I am conscious!).
Your mileage may vary.