If you have a Nokia 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.