While traveling Scandinavia I took along InaraShuffle - my trusty new iPod Shuffle which doubles as a USB keychain drive. Besides the requisite music (what? you use that thing for music) I also had my travel information and a host of Mac and Windows applications for making any internet cafe computer useful to me. It also allows my computer usage to be a little more private as my internet cache, passwords, and the ilk aren't getting stored on the hard-drive (though a keylogger would work).
I plugged in the iPod Shuffle and pulled up Firefox, an SSH client, and SunBird (for scheduling). However, a lot more of these apps have shown up, so check out the list at USB Utilities.
I think I'll definitely be adding Trillian (instant messaging), abiword (word processing), and noiseware (photo-editing).