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).
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.