Seems a little backwards to me... not much you can do in the garden while it's under feet of snow, so you might as well go ahead and get the compost started now. You will want it later!
All you need to start composting is to save your kitchen scraps etc and then look around for some browns to go with them (see the sticky on Greens and Browns at the beginning of this forum). I collected a whole bunch of fall leaves for that. If you don't still have any fall leaves around, torn up cardboard, shredded paper, torn up grocery bags, woody stems of any dead plants still around, etc, will do. You can supplement the kitchen scraps with coffee grounds free from Starbucks type places, gas stations that serve coffee, etc. Just need some kind of bin/ enclosure to hold it all in. Since you are in a cold, snowy area, your pile will likely just freeze (mine does), but that's ok, all the freeze/ thaw stuff just helps break everything down. It will start cooking again in the spring and you will already have some finished compost at the bottom of your pile by then.
Soil testing in early spring, once your ground is unfrozen, is a good idea. It will help you know more about what to do for your soil. But if you already know it is heavy clay, then you know you will need to add lots of organic matter to help lighten/ loosen that up. The compost is the best thing for that, but composted manure, and other organic material is good too. What else you might need for nutrients depends on the soil test results and what you plan to grow. Different plants have different requirements.
Mulch is really helpful, keeps weeds down tremendously as well as eventually breaking down and helping enrich, lighten your soil. A variety of choices, wood chips, grass clippings, straw, etc, some of which can be free. Since I have a lot of brush on my property, I have a little chipper shredder to turn it into my own homemade wood chips.