I am not sure how the cell phone navigation works. I suppose the map is loaded from the phone connection and location is set by GPS?
It depends on which app you use and what you have enabled on the phone.
You can selectively turn on or off the GPS, the cell phone connection, data sync over the cell connection and WiFi.
Each app that needs location data can use triangulation of cell signals, the IP address of whichever WiFi connection you are on, and/or the GPS receiver (which is the same type used in most consumer GPS products). GPS is most accurate, the others just give a general idea of where you are at.
As for maps, that is also app specific. Google maps in normal mode uses data over a real time data connection through the cell or WiFi. Go out of cell or WiFi range and you don't have a map. Google maps does have the ability to download certain areas if you know where you will be. Then if you lose cell connection it can still navigate.
GPS specific apps, like OSMand, CoPilot, Garmin, TomTom, etc will download the entire country/continent and save it to your phone (on the SD card if you choose). Then you can navigate even if you do not have a cell or WiFi signal (as long as you have enabled the GPS data, remember you can turn the GPS on or off).
To download maps, either with Google or any of the others you need to be connected to the net, preferably on WiFi. Once downloaded you have them as long as you want.
Sorry, hope this isn't too confusing.