Suggestions for wireless internet while travelling?

[Trisha Cupra]

Hi,

I'm going to be travelling around Australia in a caravan for a year 
starting 4 December. I have a laptop and I'm wondering if anyone can 
give me some advice about being able to use the internet on the road, 
and outside of metro areas.

I've heard it's hard to use mobile/wireless broadband with Ubuntu - is 
that true? What about wireless usb modems vs cards? And a good ISP that 
doesn't cost an arm and a leg for a decent service?

If I'm stuck with internet cafes, can I take my laptop in and somehow 
connect? How does it work? And can I use Ubuntu (I have gutsy dual 
booting with WinXP)?

Thanks,
Trisha