When I upgraded to my recent smartphone hardware (a Samsung Galaxy S4 running Cyanogen Mod) I noticed that the time it takes to get a first location via GPS (first time to fix) is stunningly quick compared to my previous device. Even after not having used the GPS receiver for more than half a day, it only takes a few seconds until at least 3 satellites have been decoded and a pretty good approximation of my location is being returned.
Obviously using Google's Wi-Fi SSID database gives an even faster first location approximation but I am not very fond of having to consent to periodically gathering SSID and location information for Google to return the favor. But with such a fast GPS startup time I don't need Google's SSID services anymore and thus I have happily switched it off to re-gain some of my privacy. Yes, I know, SSID location gathering should be anonymous but I don't want to do it anyway.
But getting a fast GPS fix means that the device has to ask for satellite location information which also requires a rough location approximation being sent to a server in the network in what is called a SUPL request. More about my 'adventures' to find out more about what's included in such a request in my next post on the topic.
I assume Google does the same thing with mobile networks that it does with WiFi: it just scans all radio cell IDs and records them back home, together with the location. Even with GPS and WiFi switched off, you get a pretty good location guess.