I'm flying into Melbourne, Australia first thing in the morning in a few weeks. At that time of the morning (rush hour, I assume) a taxi would be madness. What's the most cost efficient form of public transport from there to the city center?
The Melbourne airport website has a section on public transport, which basically means buses. They recommend using Skybus to get into the city centre. I've used Skybus before during rush hour going the other way, and found it fine. The price should be quite a bit less than a taxi too.
It sounds like you should be arriving at the right time to take advantage of the Skybus hotel transfer service, where they'll take you from the Southern Cross Station (where the coach terminates in the city centre) to your hotel / hostel, which should make your journey easier.
As it is, the only public transport option from Melbourne Airport (known locally as Tullamarine) to the city centre is the privately run SkyBus, which will set you back $18. The Airport is connected to the city by freeway, and you can expect congestion during peak hours.
Alternatively, you could take one of the suburban public buses which connect to the rail network, but I seriously doubt these will be faster, and won't have anywhere for your luggage.
As mentioned elsewhere, a taxi will be as fast as SkyBus since it will take the same roads and can use the express lane, and it can take you directly to your hotel or workplace. Taxis are expensive but tipping is not required.