They use Cell-site triangulation
Your phone registers with more than one cell site - usually three or more. And they can triangulate your phone based on the strength of the signal from each base station to the handset. And you don't need to make a call either. Just needs to be turned on and registered with GSM. It's called Multilateration. The cellular networks only would share the information if they had an official request from law enforcement, but I get the feeling they will just be passing these feeds on wholesale to the intelligence community for full assessment. This will be hard to wind back from the intelligence community once the government have this information, which is why the Australians are so loathe to do it.
https://en.wikipedia.org/wiki/Mobile_phone_tracking