11:13 a.m. on January 18, 2013 (EST)
Except for the other-side-of-the-world thing, you could be visiting me! Today's forecast: high of -17C, humidity 74%, winds 40kph gusting to 70. (It's ok, it'll be 0 by Sunday). There's good advice above, but if it helps, here's what I'd wear if I was ice-fishing today, instead of snowshoeing.
Most places that get that cold are also dry, but not Newfoundland, so no down insulation for me. It's not about precipitation, only an air-tight seal could keep that dampness out. Synthetic all the way. The important part is blocking the wind.
Baselayer, wool or poly zipneck. (My current favourite for supercold is actually a running jersey from Salomon, a very thin softshell, shiny outside, fleecy inside, stretchy, with mesh armpits. The little low-profile zip pockets in running clothes are very useful in winter for things that have to stay warm.) Outer layer, an Outdoor Research uninsulated Goretex shell, the kind with pit zips that go to the hem.
In between, insulation. Key item, a Polartec Windpro fleece jacket. Mine is made by MEC (Mountain Equipment Co-op, Canada). Thick, soft, stretchy, but also very, very dense, with a membrane to stop wind. So warm. (This and the goretex shell would be enough for activity.) I actually have two Patagonia Nanopuffs (I know, decadent, but they're perfect things and I love them), a pullover with no hood, size small, and a zip-front hooded jacket, medium. Today I might put the pullover under the fleece, which is size medium for this reason, and the jacket over, if I wasn't moving. The jacket can come off and pack tiny if it's too much. It probably would be.
I do own an insulated winter jacket, but I never wear it. I can move better and adapt to changing weather better in the layers. The Nanopuff/shell combo is basically a winter jacket in halves, anyway.
I can't imagine going out with only one layer on my legs. Long poly underwear, then thicker leggings, then uninsulated windproof/water resistant nylon shell pants. (Another benefit of the layering system, economy! Year-round use for uninsulated shells.)
See above for advice on feet. Most important, no tight boots. At least half size up for winter. Wiggle room prevents freezing. My Baffins have wool/reflectix liners, you can buy reflective insoles, good for standing still on snow and ice. Hands: I wear thin wool or poly gloves, and the rest is activity dependent. Thick wool or fleece mittens under a wind/waterproof shell mitten sometimes, but if I need dexterity in this weather, here's my trick: latex gloves. A nurse friend supplies me with the tough ones used for chemo treatment, but any will do, the main thing is NOT TIGHT, just snug. These go over the liner gloves and inside the mittens. (I like mittens with flip-tops so I can get my fingers out without taking off the mitten.) Then I have warm, windproof, waterproof, grippy fingers for fiddly tasks with tiny things. Extra liner gloves for swapping out if my hands get sweaty. If anybody makes a truly warm glove that lets you work knots out of fishing line at -20C, I haven't found it, so please let me know if you do!
Cripes, longest post ever. Sorry for the wall of text and probably unnecessary advice! My climate is so similar I'm compelled to offer it all, just in case something in there helps. I wish you happy travels!
Edit: Not latex! Nitrile gloves. Non-allergenic.