If you want "free" upgrades which do not require 500-milers or other sorts of upgrades you can fly either Northwest, Delta, Continental, or US.

With Continental they have partnered with Qantas, but you don't earn any elite qualification miles (only redeemable miles on certain fares). You could take the true-FTer route and go with Virgin Atlantic to Australia, you will have to connect in LHR from/to the United States. You can earn Continental EQMs with Virgin Atlantic but only on certain fares.

US now gives free upgrades and you can take United to Australia and earn EQMs.