As an Australian, I thought I'd through in a few tips:
Get 3P or Buy E+ access. It is well worth it. Try trading something on Coupon Connection.
If you want to go to MEL from SYD, go to CBR on a coach (3-4 hrs).
Then get a flight on
Tiger Airways. It is a real LCC. AU$20 each way for flights between 21 Oct 08 to 11 Dec 08.
If you want, visit some other cities on Tiger. At $20/flight you can't really go wrong and you'll probably find that getting to/from the airport will cost about that anyway.
If you're very lucky you might be able to open-jaw your free ticket, so that you do something like:
LAX-SYD
MEL-SYD-LAX
United fly MEL-SYD but only for passengers connecting to the USA.