Simone:
The trees can be dug as soon as the fall frosts kill the leaves. Dig them then, and store them with the
roots buried in a pile of sand, dirt, or
compost until the new place is available for planting. If the ground is already frozen by the time you get to your new place, store them similarly until spring. Perennials can be treated the same. You wouldn't necessarily have to wait for frost to kill the leaves.