If you get lost easily, getting stuck with poor or no signal on your phone can be an extremely frustrating experience. For my recent trip to China I needed a solid offline map on my phone.
Offline Google Maps
The simplest solution is Google Maps, which has great coverage in foreign countries. You can type "OK maps" in the search box to cache the screen you're looking at.
Working With Map Data
There are several downsides to Google Maps. You can't download huge portions of the map or save subway and walking directions. On my China trip, I planned to visit multiple destinations in 4 cities. Google Maps wasn't going to cut it.
The best solution I've found is to use map data generated by Google MyMaps along with a map app that can cache data. This allows you to know exactly where you are, without needing a internet connection as long you have GPS.
Step 1: Plot trip with Google Maps Engine
If you haven't used Google MyMaps, it's an easy (and free!) way to plot a trip. You can search for locations, save them, and write notes right on the map. Another handy feature is the ability to share the map with fellow travelers and allow them to edit it.
Step 2: Export KML
Once you have your map plotted out, export data by selecting "Export to KML/KMZ"
KML gives you a nicely formatted file with all your map data. I've written notes on some of the locations in case I need to tell a cab to go somewhere.
Step 3: Convert KML to GPX
If you app needs GPX instead of KML, convert the KML file to GPX. I've had success with GPS visualizer. Your GPX file should have the same data just in a different format.
Step 4: Import to Map App
The app I used is ViewRanger. It's free and available on iOS and Android. Import your KML file and make sure to download it for offline use. Also, these maps can be quite big. Saving Beijing took up around 100mb.
Step 5: Have a great trip!
During my China trip, the offline map was indispensable. I always knew where I was. I used it to stay on track during hikes, see if taxis were taking me to the right place, and access visual notes at each location.