Further if you're not looking for realtime direction finding and you're willing to wait a few minutes for a fix, you can get away with far fewer satellites.
Putting 6 small satellites in orbit and getting position fixes every hour would still be way better than nothing.
We already stipulated that we're landing something on the surface. That could include a stationary transmitter, which satellites could use to periodically update their location and velocity.
I think terraformed is long after we'd want GPS. Once we have any sort of Martian colony (which is usually a prerequisite for terraforming, not the other way around) and the ability to build rockets and fuel from Martian resources, it should be straightforward for Martians to set up a GPS network of their own (easier than Earth, probably, due to the lower gravity and thinner atmosphere).
Existing GPS satellites orient themselves by ground stations, so we'd need at least some ground presence. Said presence doesn't have to be manned, though.
