I think it's a bit of a misconception that GPS "corrects" for relativity in the sense that it would provide erroneous results if it didn't.
GPS provides closed-loop positions and times relative to ground-based references. The position reference is a collection of surveyed ground tracking stations run by the Air Force, and the time reference is the US Naval Observatory's master atomic clock (which is coordinated with the NIST clocks in Boulder and all the other clocks around the world that define UTC). The satellites are tracked by these monitor stations and their orbital elements are sent up to the satellites that broadcast them in their ephemerides to the user terminals. Similarly observations of their clocks are compared to the ground clocks and polynomial curve-fitting coefficients are also sent up for broadcast.
So if a satellite drifts out of its orbit, or if its clock drifts, this is detected by the monitoring stations and turned around in the ephemerides the satellites broadcast to its users. Even if Einstein had never discovered relativity, its effects would be just one of several "unmodeled errors" automatically corrected by the system. The users would still get their correct positions and times relative to those ground references.
The operators might be baffled as to why the spacecraft clocks, regardless of design and manufacturer, all seemed to run a little faster than they had on earth before launch. Eventually somebody would get curious enough about it to discover it and win the Nobel, but GPS wouldn't actually need it to work.
