Base layer fool! I've got thermal leggins and t-shirt. I usually wear 2 or 3 t-shirts over that when it's really cold. Doesn't stop the cold but takes the sharp edge off of it.
And yeah gloves, You'll feel 
better if you're hands aren't freezing.
Gloves actually have less importance than what you're wearing to keep your legs and torso and head warm. Sure, they are important too - but the thing is, if you have insufficient clothing to keep general heat dissipation to minimum, your hands and feet are the first things that will start feeling cold (apart from your face which is usually most exposed part of your body, but that's a bit different). That's because your body will concentrate on keeping the torso and head at normal temperature, and that means the circulation in your limbs will suffer, and thus you will start feeling cold hands even with the best gloves and shoes in the world. And if you can keep other parts of your body warm, then your hands will not feel as cold either.
The amount of clothing you need depends heavily on how much you can and need to be moving. If it's not cold enough, you can keep warm by moving around, walking fast and so forth, and need a lot less clothing then you might think. If it's cold enough that breathing faster starts hurting, then you simply can't move fast enough to produce heat by muscle activity, so you need to instead minimize heat dissipation. Like tinfoil said, wind needs some serious consideration too.
Ideally, you need a layer that leads moisture away from the skin, a layer that insulates (and probably also absorbs some moisture), and a layer that stops the wind. The first one is relevant only if you need to do strenuous activity in cold, leading to sweating. Although too strenuous activity in cold can lead to lung problems since you need to breathe faster than your nasal cavity can heat the air up, leading your lungs to be exposed to very cold and dry air. Anyway, cotton garments facing your skin are death since they don't really lead the sweat away, they just become wet. Wool is much better choice; it has the ability to absorb a lot more moisture than cotton and still retain significant insulation capacity.
The inuit had pretty much ideal winter clothing; basically they had the undergarments, then an inverted fur layer with the furry side facing inward, then a walrus hide anorak to stop the wind. The polar explorers ended up either researching and adopting their way of surviving; or at least the surviving parties did. Amundsen picked the Inuit style of fur and leather clothing and dogs for transportation and did pretty well, while captain Scott chose to stick with British clothing (cotton, deadly cotton...) and
ponies for their antarctic expedition which ended up in the death of the whole party.
As far as headwear goes, the importance of a properly designed and properly worn hood can't be exaggerated. It is an awesome component of your jacket and it protects your neck, head and face from both radiation and conduction types of heat loss; it reflects a lot of the heat back, and obviously stops wind, and even though the front is open, a properly set hood creates a pressure buffer in front of your face even though you might not notice it, and makes a significant difference in how cold your face becomes. A proper hat is important (a tuque or
karvalakki are probably the best choices), yes, but in
really cold conditions, a good hood becomes an absolute necessity.
Shoes are more important than gloves, too. Specifically, you need footwear that can deal with heat and moisture both. You need the shoes to be able to stop the heat from going away, but preferably be able to lead the moisture away. If that can't be achieved, then you need something that can absorb a LOT of moisture before it start to lose it's thermal insulation capacity. The former requires expensive Gore-Tex or equivalent solution, while the latter can be simply done with thick rubber boots big enough to fit removable felt-made lining parts in them, which can be swapped when they become damp. What comes to socks, wearing something like tennis socks made of cotton is about the worst thing to do. Woolen socks are better, they lead moisture away better, feel dry far longer, and cotton becomes much more rough when it gets moist, so wool causes less blisters too (though that is only an issue if you go take a hike or march...). Obviously, the shoes need to be big enough to fit at least two layers of socks inside without pressure (which causes blisters and reduces the thermal insulation and water absorption ability of your socks).
Prolonged exposure to cold also needs other things to be taken care of aside from clothing, such as making sure you don't become dehydrated. And you need to eat more than normally too, cold uses your direct glucose stores surprisingly fast. And you need a partner to keep an eye on your face for frostbites, and you need to do the same for others. Aside from the wind, though, as long as you can stay dry and retain your mobility, simply getting used to cold is an important factor in how cold you feel, especially regarding hands and face. After some time (days, weeks) with constant exposure to cold, your body actually starts to adapt to it. Your peripheral circulation improves, which makes your hands and feet warmer. On personal experience, after staying a few hours in about -20-24 degrees Celcius without gloves my hands actually started to warm up spontaneously, regained their mobility and felt warm to touch, despite conditions not changing. Not that you should do this, mind you. The reason for this particular stupidity was that I had to take notes on the performance of the conscripts in a soldier's basic test and doing that with gloves was rather impossible...
As far as what kind of gloves you should be using, again woollen mittens and separate, thick thermal insulation mittens/gloves on top of them have worked fine for me. If you need more mobility, then leather gloves are probably best... Thick gloves with separate fingers have almost no point at all, since you lose the ability to manipulate stuff accurately with those gloves anyway and they are thermally inferior to mittens with one section for thumb and one for other fingers.
