Australian postal employee checking in here (dontcha just love the SDMB?).
OK, with the amount of mail between the US and Australia measured in tons, it is basically impossible for me to tell you exactly how long one individual article will take to make the trip. Theoretically, a week should be plenty. The thing to remember with mail is not so much the distance, as the number of times it must be processed before it gets to its destination, ie a letter between any two major US cities will be pretty quick because all they have to do(more or les) is throw it onto a plane. A letter going from a small town in California to a cattle ranch in Texas may be a different story because it’s going to have to transit more places. Ideally, Melbourne is just another big city with direct mail links, so you’d only need to factor in an extra day for the trans-Pacific flight. The truth is usually another story though, so with any “mission critical” documents, I’d not be using regular mail. The USPS and Australia Post both use the EMS system. It’s considerably more expensive than regular mail, but probably less so than the private carriers. EMS really does get processed separately to normal mail (it’s not just a scam). It’s first on the plane, and first off. It pretty much gets the royal treatment all the way. If I were you, I’d ask your local post office about it. The USPS also operates a slightly cheaper express service which would probably also suit your needs.
Australian mail processing is highly automated OCR technology, so it’s important to have the address exactly right, otherwise the article could be rejected by the machine, and sent to manual processing. This could possibly delay it.
Australian addresses make no distinction between a suburb of a major city and a town on its own. In other words, if you are writing to the Melbourne suburb of Richmond for example, you would just write “RICHMOND VIC 3121” with no mention of Melbourne. The Australian machines / sorters will know what to do with it. Only use “Melbourne” if your letter is actually going to central, downtown Melbourne. That’d be “MELBOURNE VIC 3000”. Many people write “Richmond, MELBOURNE” thinking they are better clarifying the address, but all that happens is it gets sent from the airport to central Melbourne unnecessarily.
The correct format is:
Joe Bloggs
12 Kennett St
RICHMOND VIC 3121
AUSTRALIA
The suburb and state abbreviation should be capitalised. Make sure you know the postcode. If you don’t, email me.
I hope this doesn’t sound overly complicated. You can get away with all sorts of errors in the address, and it’ll still get there, but if you’re paranoid about this thing arriving on time, then it can’t hurt. 
But really, check out the EMS service. I’m pretty sure it’s called the same thing in the US.