If you have a Nokia Symbian device, then you can get Ovi Maps installed on it. Ovi Maps allows you to download map files for as many countries as you want and store in on your memory card. Once that's done, you can set Ovi Maps to offline mode and still be able to use it to get directions. If you get a local SIM, then it will be able to show you rough location data too.
I find Google Maps' public transit planning feature very handy too but I often cannot use it on roaming. Instead, I use this app called Métro (available for iPhone, BlackBerry, Symbian, Windows Mobile, PalmOS - no Android or Windows Phone 7 version yet) that allows you to store public transit information data offline for many major cities around the world. The full list of supported cities supported by Métro is available here; you can also use the same page to customise your download in case you do not want the full package. They are fairly regular with keeping their database up-to-date too.
EDIT: Google Maps has recently launched a beta feature (only on Android phones though) that allows you to save map data for a specific radius on your phone for offline usage. Not as useful as downloading maps for a whole country like Ovi Maps allows, but if you have wifi access every now and then on the road then you should be able to take bits of Google Maps offline on the go.
EDIT 2: Android users can also try out the free MapDroyd app that allows you download offline maps country-by-country. The maps themselves are mostly barebones with no point-of-interest data.