The electronic visa for Australia is A$20, and you can get it on this Web site:
http://www.eta.immi.gov.au/

I got two of them instantly online earlier this year. They don't give you anything on paper - it will just show up in the immigration officer's computer if you've received one.

Since you're going to have such short notice, award travel is always a good option - if you've got the miles. Otherwise, you have to just hope there's some special airfare available. You might also try calling up some consolidators to see if they have anything.