You can plant them when it's still frosting out, but not when it's still freezing regularly. Until then, keep them in the coolest, darkest spot you have inside. An unheated basement or garage is perfect. A large shed should work too, if not too drafty.
If it's too warm, they will put out shoots and start growing, which isn't fatal, but can cause severe setbacks once planted. Between 32 and 45 degrees Fahrenheit is ideal for this, the colder end being better.
In my area, I usually heel them into a trench and fill it with mulch until planting time, but I live in a warmer area where the ground doesn't freeze nearly as hard or as deep as where you are, so this will likely not be a solution for you.
If the roots are still bound (for shipping), free them, cut off anything snapped or ragged, and put them in damp sawdust/sand/peat/similar medium. They may sprout a little by May 5 (you can plant them before the last frost, btw), but it shouldn't be too bad if you have a cold spot. Just plant very carefully if they have even small sprouts, as they are easy to break off.