I've tried this myself, actually. I go hiking quite regularly, and my phone has GPS, so I've tested it out once or twice. The trick is that your location is calculated by talking to the GPS satellite network, which has pretty decent signal everywhere (although accuracy decreases slightly as you get closer to the poles because of the spacing of the satellites). Unfortunately, that's just your co-ordinates; latitude and longitude. To locate yourself on a map, the map has to be downloaded, and that requires some kind of cell connection - preferably a 3G or 4G signal. You can download the maps ahead of time, and most map apps will cache maps so if it's within the same rough area as somewhere you've looked at before (especially recently), it may still be in memory. Some apps come with internal map data so they don't need a cell connection, but they're often quite large downloads and will take time to install on your phone (I have one that took half an hour to download over my home WiFi).
It's also worth noting that the internal GPS receiver on a phone is not as big or sensitive as the ones you get on proper hiking GPS devices, so you may well have trouble getting a stable signal. Things that can cause you to lose signal include: bad weather, overhead cover (very dense trees, caves, buildings, that sort of thing), electrical interference (power stations or substation transformers, lots of power lines nearby, being within a few feet of a running car engine). You'll also have trouble if you have limited line-of-sight to sky (if you're between tall hills or in a ravine, for example) because the satellites are rarely precisely overhead - the triangulation works best when they're spread out a bit. The more sky you can see, the more satellites you'll be able to connect to, and the better the fix you'll have. You need at least three satellites for a position; the more you have, the more accurate it'll get.
On my phone, here's some typical performance in countryside:
- Thirty seconds to a minute for a fix, after turning the GPS on. (This is known as "cold start" if you want to look up more detail.)
- Usually starts off by giving me a ~100m circle as it acquires the fix, which narrows down to ~10m in two to five seconds depending on the number of satellites it can see.
- Usually you'll get between 5 and 8, maybe 9 (at my latitude, anyway - about 50 degrees). Not all map apps will tell you this statistic.
- With 5 satellites, 10m is about the best accuracy it gets, maybe a shade better; with 8, it's down to about 2 or 3 metres, which takes about 5 - 10 seconds after that first fix, which means a total of 40 seconds up to maybe a minute and a half for it to be settled and really ready for use.
If your character needs to use their phone to get to this place, then you'll need one of these conditions:
- Decent cell connection to download the maps
- The character has looked at the area on his phone map app before (sometime when he had an internet connection) so the maps are loaded
- The character has a proper hiking maps app installed on his phone (rather than just Google Maps or whatever) so it has the maps stored on the phone
- As a last possibility, he has a set of co-ordinates to get to, so he can use one of the GPS apps that reads out your co-ordinates, allowing him to tell whether he's going the right way, but not what the terrain looks like.
If you want him to get there, but be lost for a while along the way, then in a fairly dense forest away from towns and cities it'd be entirely plausible for him to have bad cell reception so he has to wait (or wander around a bit) to get enough signal to download the next patch of map. Note that many systems will download in chunks at varying zoom levels, so it might be that he has a zoomed-out, high-level map of the area, but when he zooms in to get better detail, it pixelates and he has to wait ages for the zoomed-in version to download - or maybe it doesn't, and this lack of detail in the map is why he takes so long.