It really depends on how much coverage you need, and how much you spend
per month.

Also, you may need a new mobile, depends if your current one that you
use in the US is triband or not.

If your a heavy spender, I suggest one of Vodafones caps.
They have a $49 cap, which gives you $230 worth of standard calls, SMS,
MMS and more and you only pay $49 a month.
They also have a $79 and a $149 cap, which gives you $500 and $1200
worth of standard calls, SMS and MMS and you only pay the cap price.
You can choose to pay through Prepay, or just a normal bill in the
mail. If you say only use $36 dollars one month, you'll only pay $36.
But if you use say $100, you'll pay the price of your cap, eg $49.
Vodafone also offer normal Prepaid. Vodafone are also good because they
charge by the second, not in 30 second lumps. You can check out
vodafone's coverage maps on www.vodafone.com.au 

If your a light spender, 3 has a $29 cap which gives you $120 worth of
calls. 3 has 3G coverage only in Melbourne, Sydney, Perth, Brisbane,
Adelaide and soon to be Canberra. Once your out of this coverage zone,
you fall back on to Telstra's GSM network, which 'suposedly' has the
best GSM coverage in Australia. I'm not sure about this, so please
correct me if im wrong. Once your out of 3's coverage, you can only
make/recieve voice calls, sms and mms. When your in 3's coverage, you
can make video calls, access 3's services, voice calls, sms and mms.
The drawback with 3 is that they only have 3G services in the city, and
inner suburbs, and you have to buy a phone from them to sign up for the
service. Three's website is www.three.com.au. They also offer 3
prepaid.

You can also go on Prepaid, if you prefer not to have a bill. You
simply buy a starter kit from say a supermarket, on Telstra, Optus,
Vodafone, Virgin Mobile or AAPT. for usually $30. Comes with $30 worth
of credit, and a simcard. Pop the simcard in your phone, ring up the
number on the pack, give them your details, and your done. When your
credit runs out, simply go to a petrol station, supermarket, a mobile
shop that sells your carriers mobiles etc, and ask for a recharge. They
usually come in denominations from $15 - $100. And you can continue to
make calls.

A very good company is iSim and I suggest their prepaid service. They
run on Optus' network so you get good coverage, and they offer a cheap
call rate. Check out their website at www.isim.com.au. You have to sign
up online for iSim. They dont charge flagfall, and calls are charged at
at a flat rate of 39c/min, billed per second, 15c SMS and 19c/voicemail
retrieval.

Hope this helps,
icedark

There are three GSM networks, operated by Telstra, Optus and Vodafone.
There is one national CDMA network, operated by Telstra.

GSM coverage is aimed at urban areas, gets a tad thin once you get out of the
smog, and despite claims of 90-whatever percentage population cover this
translates to pathetic area cover in the boonies.

CDMA replaced the old AMPS analog service that would have been here in your day.
Boonies coverage has been stepped up but it still has a loooong way to go here
in WA.

Coverage:  Telstra, Optus and Vodafone in that order - but it obviously varies
from place to place.  T & O are fairly close, but V are a fair way down once you
get outside the metro area.  Don't believe any of the coverage maps - they are
full of wildly optimistic claims.  (Take only after meals, with a bucket of
salt.)

Price:  Depends on your usage.  For the basic phone/SMS services for a budget
(low outgoing aka "glovebox" user) the current best around is iSim (wholly owned
subsidiary of Optus).  One of the (very) few with no flagfall, and 39c/min IIRC
billed by the second.  This is a pre-paid plan.

As your volume goes up, there are a veritable raft of alternate plans offering
different features (aka marketing gimmicks).  You really need to define your
usage pattern to be able to get much further.  Then do the maths to see if a
capped plan gives you a better cost/month than say iSim.

Watch the billing basis - many plans bill by the 30-sec or 60-sec block or part
thereof.  When you add flagfall and the "block" cost, there is a dramatic
difference in costs for short call operation - the "Dad, I'm down at the bus
stop,  Can you pick me up?" stuff.

Assuming you have returned sans handset, most operators provide numerous plans
with bundled handsets.  Not always the best way - often to buy outright at a
competitive price and bring the handset into a SIM-only plan is noticeably
cheaper.  Also most operators' bundled handsets are network locked or SIM
locked, with a penalty for leaving their network.

Just my 2.2c worth - which raises one last point.  Aus has a 10% Goods &
Services Tax introduced on 1/7/2000 which will in most cases be added on to
whatever plan/call prices you see.  Very few operators actually quote the
tax-inclusive price, preferring to have a small asterisk leading to an even
smaller footnote which says "plus GST".

Welcome back to sunny(?) Perth

True, Vodafone is good along highways, and it really does depend where
you are, but when im not on a highway, and really out in the bush, I do
find Telstra and Optus better. Although I did find one time, in one
remote spot, Vodafone had 3/4 coverage, and optus and telstra had none.
Just depends where you are.

Also, Vodafone does now roam onto Telstra GSM but only if you are on a
plan.
http://www.vodafone.com.au/rep/coverage/national_roaming.jsp?gs=foryou&hd=covera
ge&st=australian&ss=national_roaming