Hi again.
Look at realestate.com.au for a good idea of how much renting can cost in the different cities -
you should be able to get an appartment cheaper than $1000/month, just depends where you want to be.
I'd expect the biggest cities to have the best j2ee opportunities - I'm in Brisbane (not the biggest) and it seems there are lots more jobs in Sydney, Melbourne and Adelaide - have a look on seek.com.au or jobserve.com.au to get an idea of what's out there.
Most of the jobs on these websites seem to be going through consultants - I guess they'd be the ones to ask about things like travel expenses. I'm always hearing about the IT skills shortage here, so I wouldn't be surprised if they offered to help out with relocation expenses.
The main thing they're looking for is your visa - mine hasn't arrived yet, so I can't work until it does (sob!) but it looks like when I get it, there will be a lot of Java/J2EE jobs, even here in Brisbane.
Can't help much re interviews, as I can't really go to any yet - again, send a few emails to the agents you see on the jobsites - I know some do interview sessions in other countries, but obviously it's easier if you're here. Are there any companies where you are that have offices in Oz? If so, surely that would be the easiest way to get in.
Re commuting - the public transport here in QLD isn't great, but I think it's a lot better in other places. You could easily arrange a place to live where you could use buses or trains to get to work.
Good luck with it all - hopefully my visa should come through in a month or two, so I'll get some better experience of interviews then! I'd definitely recommend mailing recruitment consultants - they have the experience in getting people over here to work, and the ones I've spoken to have been very friendly and helpful.
Take care, and I hope it works out for you.
Rick