Not sure if you'll have to change you cell network everytime you reach a different country or not, depends on that networks coverage and your phone.
I have little experience with PDA's but i have had a PC or two running out of the back of a van. I just connected PC to my phone and hey presto.
Connectivity using mobile networking in the UK is pretty crud IMO so you have to watch out for dips in the service or you could lose out. I dont what its like in anywhere outside europe, but be prepared to not get connected at all in some places.
And always have loads of batteries, and a charger that you can plug into a cigarette lighter (in car), and a spare phone cable for hotels and stuff.
Probably not much help really, but google wireless/mobile networking :) Look at the bright side you back at the top of the queue now.