Oceania (Australia, New Zealand & the South Pacific) - First time to Australia

Hello all! First time poster here, so forgive me if this should be in another forum.

In February I'll be taking my first trip to Australia, probably going Nashville-Melbourne and back, although I'm watching prices to see if Atlanta - Melbourne is significantly less expensive (it hasn't been lately). I've got a million questions, but the first is the most basic: tips and tricks for grabbing the best possible flight (cheapest but with decent service) for this? It will be myself and my wife on the ATL-MEL leg, and then we'll be returning at different times (she in one week, myself in two).

I'll be traveling internally around Australia on someone else's $ after she leaves, heading MEL-SYD and then SYD-Perth. Ideally, I'd love to be able to just fly Perth-Nashville and not have to head back to MEL for the return...but in looking at tickets it seems the MEL leg is going to save me $. Is there something I'm overlooking? In an absolutely awesome world, I'd figure out how to do something like Perth-Tokyo-USA on the return flight and do a couple of day layover in Tokyo (dying to see it, won't be on that side of the planet very often). Is that even reasonably affordable re: tickets?

Any tips would be appreciated, everyone. I fly monthly in the US, but very rarely internationally, and this is by far the longest hop I've done.

Thanks in advance!

Welcome to the forum !

As you are looking at the cheapest fare can we assume you will be in economy ?
Do you have status on any airline or a preference for a specific airline freq flyer miles ?
Many options on airlines (United, Qantas, Virgin, Delta, Air NZ, Hawaiian) & route (http://gc.kls2.com/cgi-bin/gc?PATH=bna-lax-mel%0D%0Abna-dfw-bne-mel%0D%0Amel-per%0D%0A&RANGE=&PATH-COLOR=red&PATH-UNITS=mi&PATH-MINIMUM=&SPEED-GROUND=&SPEED-UNITS=kts&RANGE-STYLE=best&RANGE-COLOR=navy&MAP-STYLE=).
Also look at RTW & circle pacific fares

How long is Australia?
Australia is big Australia vs USA map (http://www.anbg.gov.au/maps/aust-usa-map.jpg)

If price is no object then you'd want to be flying QF on the domestic Australia segments. PER is quite far from MEL (similar to US transcontinental) hence the higher air fares. Returning via Europe is about the same distance from PER as trans-Pacific, and while RTW fares wont generally be cheaper they do allow much more travel (miles) and flexibility (you could include some or all of your Australian domestic travel in the RTW fare, for example, and maybe get it partially reimbursed). The Oneworld Circle Pacific fare would allow routing ATL-LAX-MEL-PER-HKG-NRT-ORD-ATL etc. If it is any consolation US-Australia fares are 30% cheaper than Australia-US fares (on same route/day/airline, just flying in the reverse direction), so you are getting a better deal than Aussies visiting the US.