I used Chessmoving to move from Sydney to Melbourne in 2008. They have a number of locations in all states/territories. These guys did a great job.
Easiest thing to do is to search online for customer reviews. Then obtain a number of quotes from a number of companies. Then decide who to go with. Quotes vary depending on what you want - ie. packing yourselves, have the company pack for you, level of transit/storage insurance, etc.
