I think only the top inch or so of the soil freezes and the deeper you dig the warmer it gets. So when the inclement weather comes they head for Australia (from a UK perspective).
I don't know if this is a definitive answer, but I shifted about 120 tons of topsoil with my truck today. I noticed that there were a load of worms in it (so did the Pied Wagtails!). I can only assume that they 'sense' the ground freezing and go deeper.