Can we use GPS in orbit at the moon? What about on Mars?
GPS is regularly used in low earth orbit.
It is possible to use the signals from the sidelobes of the GPS transmit antennas to receive service in a high earth orbit up to and potentially beyond geosynchronous altitude:
(Image credit: GPS World)
GPS navigation has been demonstrated from HEO during an extension of the GIOVE-A mission. I haven't been able to find any reports of attempted reception at geosynchronous altitudes.
The moon would be a real stretch (though it has been proposed and simulated), and reception at Mars is completely out of the question. However, it should be noted that navigation of deep space probes including those at Mars is made with similar fundamental techniques to GPS (i.e. autocorrelation of long pseudorandom bit sequences).
GPS is since a few years used by satellites in geostationary orbit. Check out for instance this paper by Lockheed Martin about GOES-R, from the ESA GNC 2017 proceedings: https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20170004849.pdf
While I can't fully address this I can give part of an answer:
If you're looking at 4 satellites there are actually two possible solutions to the equations. Normally you can reject one because it's far out from the Earth is on or very near the Earth's surface. If you try to use it out in deep space you can't make this assumption and thus a fix will require five satellites, not four.
Furthermore, the farther from Earth you get the more closely grouped the satellites will become from your vantage point and thus the more inaccurate the fix.
I'll leave it to others to determine how far away you can get before the signal is too weak and if the satellites themselves have antennas that direct their energy earthward (which they very well might. A directional antenna cuts the power needed for the transmitter and thus the area of the solar cells needed to power it.)
Note that most civilian units do not function in space, period. This is a design decision, not a technical limitation--it keeps some black hat from using one to guide their missile. Some of them shut down at altitudes low enough to cause problems for people sending balloons to the edge of space.
Mars is definitely out of the question for the fact that it is too far, and even if signals can be obtained with some insane match filtering algorithm, the geometry of the GPS satellites would be too horrible for you to trilaterate any position with feasible accuracy. By geometry, I mean that you would be too far away that every line-of-sight vector to the GPS satellite constellation would almost be pointing in the same direction (same unit vector)!
The Moon is an interesting case. Recent simulations on new GNSS hardware have shown that we can actually receive side-lobe signals on the lunar surface, although at a very low SNR. Thus, we'd need GNSS receivers with a much larger sensitivity than our Earth-bound ones. For scale, a GPS satellite roughly ranges 20,000 to 26,000km to the Earth. In the best case where some N-th GPS satellite lines-up in-between the Earth and Moon co-linearly, GPS signals need to travel ~ 360,000km to reach the Lunar surface! Nevertheless, there is some work on it. See the references below:
You may be able to get much further out. It depends on exactly what you mean by "GPS" and how soon you need it. There is a mission on the International Space Station right now that is working on a new GPS. In this case, the "G" stands for Galactic! The mission, NICER, is primarily intended to study neutron stars. However, as stated in Ref 1, "... in addition to its science goals, NICER will enable the first space demonstration of pulsar-based navigation of spacecraft, through the Station Explorer for X-ray Timing and Navigation Technology (SEXTANT) enhancement to the mission, funded by the NASA Space Technology Mission Directorate's Game-Changing Development program".
Ref 1 NICER data sheet https://heasarc.gsfc.nasa.gov/docs/nicer/