OK, I'm back.

Nearly everything in Australia costs at least twice as much as in the US, with the overall costs ending up far more than anywhere else I've traveled. Intercity transport costs were an early clue, but this is also applies to local transport costs (nearly $4 for a single ride on urban metro systems), restaurant food (almost impossible to eat non-fastfood for under $10), fast food ($3 for McDonald's crap that's on the 'dollar menu' in the US, $7 for a fast food meal), grocery store food ($4 for a 2L of soda), etc. Tourist attraction costs are harder to compare, and I didn't end up spending much on these with my budget so blown by basic living costs, but $35 for a tour of the Sydney Opera house or $100 for a one-day tour from Melbourne to the Great Ocean Road both seem pretty steep to me. Many merchants also had surcharges of as much as $5 for paying with a credit card, which would have been very annoying if I didn't have an ATM card with a good exchange rate.

There were a few things cheaper or not much more expensive than in the US, but these were mostly reflections of categories where the US is unusually expensive by global standards rather than of Australia actually being cheap. These included Thai food ($10 a meal), prepaid 3G data ($2 a day, absolutely worth it to avoid the $5/hour internet cafes), and backpacker accommodation (around $25 a night for a dorm bed, but of pretty low quality by global standards at that price, no aircon, typically no screens in windows, etc). As ryanbryan pointed out, the lack additional tax and tip does help, though some people seem to tip anyway.

After taking such a beating the wallet, one finds oneself attracted to free attractions and activities. Australia does okay on this front, e.g. Sydney Botanical Garden is free, beaches are free, Sydney and Melbourne are beautiful, fascinating and multicultural cities worth spending time walking around for free, public toilets are reasonably common and free, etc. People mostly seem friendly and laid back; it's a pity you have to feel like they're constantly trying to rip you off. (One restaurant said I couldn't have tap water with my meal without paying extra!)

After flying back from PER to SYD, I learnt that I would have to pay $5 for the train to get from the Domestic to the International terminal at SYD in order to connect to my onward flight out of the country. Unwilling to accept this final indignity, I walked 4km along the road between the terminals instead.

I was told by people living there that over recent years, prices of goods denominated in Australian dollars have been rising quickly even as the value of the Autralian dollar itself rose relative to other currencies, and that it had reached the point where the Australian retail industry was suffering because nobody wanted to shop at such high prices. In a global economy with oil priced in USD, this seems unsustainable; surely at some point Australian prices will drop back into line with the rest of the developed world. To be honest, I'd suggest that all but the "1%" for whom money is no object consider waiting until then to visit Australia.
I took an overnight bus from Sydney to Melbourne and an overnight bus from Melbourne to Adelaide. Given the somewhat higher fares for flying, the hassle and cost of getting to the airports at either end (e.g. $15+ each way in Sydney), and the money I saved not having to book a hostel those nights, I have no regrets about taking the bus.

What are you even doing in Budget Travel? I've ridden overnight in seats on trains in every inhabited continent, and not found it anything to complain about. On this trip I rode the train from Adelaide to Perth (two nights, one day); the seats were big recliners, at least as nice as one might find in domestic airline business class, and there was even an onboard shower in the carriage.
This argument seems kind of like saying "Don't even think about flying!" The world is an unsafe place and you can be robbed or murdered while walking down the street too. A study by the California Highway Patrol found no evidence that hitchhikers are overrepresented as victims of crimes or accidents relative to their numbers in the population; I'd find it very surprising if the risk of violence in Australia were higher than in California. As I said, I've had great experiences hitchhiking in other parts of the world, and would have had no qualms trying it in Australia if I'd needed to travel a route where it made sense; the distances I was covering and my relatively limited schedule meant that it didn't on this particular trip.