This is why you must do some trip pre-planning, maybe look at a paper map or other map services before you leave so you have an idea of where you are going in your mind (and follow the road signs!). Also, I wouldn't rely on online mapping software such as google/apple maps anywhere outside of town as reception is spotty, or non-existent.
You can get proper offline navigation apps that work just like a GPS unit. My GS3 came with Navigation by Garmin and a free map download, though I haven't had the need to properly test it yet.