I finally came across this which seems quite authoratative with some interesting graphs and stuff about the various factors that affect GPS accuracy. The final section on the page: "Relativistic effects" is worth quoting verbatim rather than attempting to paraphrase (and get it wrong):

As we already learned, the time is a relevant factor in GPS navigation and must be accurate to 20 - 30 nanoseconds to ensure the necessary accuracy. Therefore the fast movement of the satellites themselves (nearly 12000 km/h) must be considered.

Whoever already dealt with the theory of relativity knows that time runs slower during very fast movements. For satellites moving with a speed of 3874 m/s, clocks run slower when viewed from earth. This relativistic time dilation leads to an inaccuracy of time of approximately 7,2 microseconds per day (1 microsecond = 10-6 seconds).

The theory of relativity also says that time moves the slower the stronger the field of gravitation is. For an observer on the earth surface the clock on board of a satellite is running faster (as the satellite in 20000 km height is exposed to a much weaker field of gravitation than the observer). And this second effect is six times stronger than the time dilation explained above.

Altogether, the clocks of the satellites seem to run a little faster. The shift of time to the observer on earth would be about 38 milliseconds per day and would make up for an total error of approximately 10 km per day. In order that those error do not have to be corrected constantly, the clocks of the satellites were set to 10.229999995453 Mhz instead of 10.23 Mhz but they are operated as if they had 10.23 MHz. By this trick the relativistic effects are compensated once and for all.

There is another relativistic effect, which is not considered for normal position determinations by GPS. It is called Sagnac-Effect and is caused by the movement of the observer on the earth surface, who also moves with a velocity of up to 500 m/s (at the equator) due to the rotation of the globe. The influence of this effect is very small and complicate to calculate as it depends on the directions of the movement. Therefore it is only considered in special cases.

Which shows that everything is relative, including (my) understanding :)

The final solution to all the relativistic affects (except the last), running the on-board clock a little slow but treating its output if it was running at the 'right' speed, is so incredibly simple it beggars belief.