It turns out they’ve all gone to Queensland.
The above is from the ABS Year Book Australia, 2008 and, sucker for stats that I am, I’ve been checking it out. This diagram actually refers to the interstate migration from 2005-06, and so it shows some of the migration to W.A. that drove the property boom that happened around that time.
Amusingly, every state is sending a significant number of people to Queensland (in particular, NSW). But there isn’t a significant number of people moving to NSW from anywhere. If people weren’t having babies, or migrating to NSW from overseas, it would be going backwards.