This depends on the planet. The technique could be different depending on the world you have in mind, as they could vary in magnetic poles, true-north poles, daily rotation, etc.. My answer, like the others here, assumes Earth, or a very Earth-like world.
GPS coordinates generally come as a pair of numbers. One number, the latitude, tells how far you are between the north and south poles from negative 90 degrees to positive 90 degrees (or 90S to 90N). The other number, the longitude, tells where you are in the other direction from -180 to +180 (180W to 180E), where around the circumference of the world you are.
Both of these numbers are generally given in 1 of 2 forms: DMS (Degrees-minutes-seconds), or as a decimal number. The latter is simple: 3.25 degrees north latitude is just what it sounds like, a quarter of the way between 3 and 4. DMS divides it up into smaller units, where there are 60 minutes in a degree and 60 seconds in a minute, so 3.25N equals 3 degrees, 15 minutes, 0 seconds N.
Latitude and longitude can be measured without any need for any map or compass. Sure, having these tools would be nice and allows you to take short cuts, but it is not too difficult to re-invent this wheel when necessary. However, you must measure latitude and longitude separately, very differently from each other, and even though it's not difficult conceptually to understand longitude measuring you do need an accurate clock.
Latitude
There are multiple ways to measure latitude. I will focus on the stars since they are easier to remember and the most reliable as long as the night is clear.
In the northern hemisphere, measuring latitude is as simple as measuring the angle to Polaris, the north star. Straight overhead means you are at the north pole (90 degrees north latitude), and straight out on the horizon means you are just above the equator (nearly 0 degrees latitude). Between the two, you just measure the angle of the north star in the sky, and that literally and directly tells you your latitude. North star 30 degrees up? You're at 30N. 50 degrees? You're at 50N. In fact, you can roughly estimate your latitude just by eyesight with no tools at all. Using a quadrant, sextant, or similar device will help you measure more accurately and finely.
You can literally use a protractor for this, and hang a string from a weight to help you estimate what is straight up/down to help measure against. You can also create a quadrant out of paper by cutting out a quarter-circle and measuring off the degrees on it and sighting along the edge.
How to Find the North Star
In the southern hemisphere, the process would be similar, except that there is not a bright star directly above the south pole, unfortunately. Instead, you need to estimate the south pole point in the sky and measure against that. You can estimate it by using the "southern cross".
How to Find the South Celestial Pole
When close to the equator it is a little bit different. I think you might be able to use the constellation Orion for that. I will look into that and get back to you for that.
Longitude
To measure longitude, you have to pick a spot around the earth's circumference to call 0 degrees. Right now, the standard is that 0 degrees longitude, called the "prime meridian", is the line between the north and south poles which passes through the royal observatory in Greenwich.
To calculate longitude, you keep track of the time at the prime meridian, and you calculate the difference between that time and your own, generally at a well defined time such as noon.
There are 24 hours in a day as the sun goes overhead around the entire planet (due to the planet rotating). You can use basic algebra to equate those 24 hours into 360 degrees of a circle around the planet. So each hour difference equals (360/24) = 15 degrees.
Example:
So you have a pocket watch whose time is set to the local time zone at the prime meridian. You want to know your longitude, so you measure shadows to figure out when the sun is at the very highest point in its arc over your head for the day, as that is the exact moment of noon at your location. Noon at your location coincides precisely with 10:30 on the watch, so there is a difference of 1.5 hours. At 15 degrees per hour, that means that your longitude is (15*1.5) = 22.5 degrees, or 22 degrees 30 minutes of longitude.
Hopefully you still have a watch around. If not, you might have to measure latitude only.