From the USDA zone map, I'd guestimate you're somewhere in either a zone 5 or maybe a zone 4 area. That assumes you're not on a higher mountain slope where the temperatures with plumet even lower. Your best bet I think will be apples, which have a few varieties that go all the way down to zone 2 hardyness. Van Well is a good nursery, and I have their trees in my orchard right now. Another good western nursery that sells the kind of stuff homesteaders crave is
http://www.burntridgenursery.com/fruitingPlants/index_product.asp?dept=17&parent=7
I through out some names that are amonst the most cold hardy that might perform well in your area. For apples, look at Transparent, Gravenstein, Honeycrisp, Spartan, and Norther Spy. As Eric mentions try to get Antonovka rootstock. It's the most cold hardy. Montrose apricot, Reliance Peach, and Vetern Peach might work. For plums, skip the Japanese, but look at European plums like Stanley, Superior, and Green Gage. A few more choices might include American persimmon, and Northstar Cherry.
Site selection might be very involved. In general, for cold climates, plant on the north side of a hill. The south side warms faster and stimulates earlier bub-break. You don't want that. A northern slope will slow budbreak till after late killing frosts have passed.
Good luck,
Michael
