There's numerous questions on this already - see
To rehash, assuming you're using a GSM phone (the standard in Europe, Australia/NZ and a bit of Asia), you have two main options - AT&T or T-Mobile. AT&T is the better network of the two, and is the most compatible with GSM phones. It is also the more expensive option. See http://www.att.com/shop/wireless/plans/prepaidplans.html
T-Mobile run their 3G network on different frequencies (1700MHz AWS as opposed to the more common 850MHz and 1900MHz used by AT&T) and your phone may not be compatible with the 3G network and hence will fall back on to the slower 2G network (Google will tell you what frequencies your phone is compatible with on which network type). They have been slowly changing their network to allow 3G on 1900MHz though, so it may work on 3G in certain areas. As mentioned in the comments, T-Mobile is the cheaper option.
Either are easy to obtain - simply go to a AT&T or T-Mobile store and purchase one. If you tell them you're travelling, they generally won't ask for any personal information besides your name (especially if you visit stores in common tourist cities). They have SIMs available in the various sizes. I'd suggest looking up where a store is before arriving at your first destination; they're generally in most big malls, but occasionally, they're not. I wouldn't try your big-box stores like Walmart or Best Buy unless you have to.
To recharge, you can get recharge vouchers at 7-Eleven stores and most of the drug store chains.
If you're adventurous, you could try the cheaper MVNOs (providers that resell access to a network like AT&T or T-Mobile) like Straight Talk. You'll probably encounter issues registering though, because you're not a resident.
Finally, try finding and downloading a mapping app that uses OpenStreetMap data (OSM for short). These apps will allow you to download the free mapping data for use offline, usually organised by city. They're not as detailed as the Google/iOS maps, but in emergencies, they'll suffice. Or buy a cheap Nokia Lumia phone and have nicer offline maps bundled :)