I'm with Telstra and for me they have the best coverage. As for Packages it will depend on how much data you use and how many phone calls you make. If you look at your current mobile bill and see how many calls you make and how much data you use that will give you a starting point. Don't forget that there is a lot of free wifi in certain places so that will help reduce your usage.
Good luck and enjoy the travels

Brett

We have 3 smart phones.

One is Telstra Phone called "Dave". The benefit is you can have a car cradle for it with an external aerial and get better reception in fringe areas. We only use Telstra pre-paid as Telstra is the most expensive Telco - you can go into any Servo to top up the credit from $10 upwards.

Our other two phones are Optus which are post-paid (a set amount each month which is cheaper than pre-paid). Coverage is good in metro areas and theyre much cheaper than Telstra. Vodafone is another Telco to consider in metro areas

Also you can take existing number.

Telsta has the best coverage by far for areas away from major cities and the east coast so like most others its our choice when travelling.    Because we only travel part time we have found the prepaid long life internet works for us, but it probably wouldn't be my choice if I was full time travelling.    

Boost is the only other company that gets the full Telstra cover.   Others such as Aldi use part of the Telstra network but not the full network, the places it doesn't work is away from the cities, making it unsuitable for travellers.

The boss has a $75 plan, not locked in, that gives her about 13 gig net and unlimited calls and text. it can be data shared
we have 15 gig wifi about $100.
I have $30 prepaid which is way to much.
I know some will be OMG but it is what we do. I do a bit of internet work on the road and we Skype with grand kids a lot.
All with Telstra
we have two lap tops, a galaxy tab also

We use Telstra Mobile WIFI plan, it is actually a Bigpond plan which is no longer available, 15Gb per month for $69.00. Telstra is $105.00 now plus with Tesltra you get slugged $10.00 per GB you are over on your plan. We also use Boost prepaid $40.00 pm which gives you unlimited calls and txt plus you get 3Gb of data plus 2 Gb of data each weekend, so you actually get 11Gb of data which we Hotspot off our phones on weekends to update systems, apps and download important documents. Use Optus it sucked in the rural areas, but saying that sometimes it had a better signal than Telstra but not very often and Vodacrap, nothing outside metro or large rural towns. When and if Telstra pull my plan I will go with the 8 Gb plan and continue to use our Boost as hotspots on both our phone, that would be 30Gb per month for $169.00 which is bloody good when you check all the other costs from other suppliers. If you are only a small user then just get a Boost prepaid $40.00 option and you won't need to have a internet plan, just make certain you have a phone that you can attach a aerial to for better reception in remote areas.

Phone is with Telstra - prepay $30 a month, $700 national calls/texts, $200 for international, 1.5gb data (used mainly for maps & tracking down phone numbers while on the go).

We have a Telstra modem, which we use rarely. for the main, we use Virgin, $40 a month for 15gb, which does both our surfing need (mainly news, family catchup on the dreaded Facebook & emaail) and my school requirements (degree through UTas). Telstra offers better cover, but along the Eastern seaboard, Virgin is fine for internet run through Optus.