In theory you could with say google earth, google maps, a good compass, landmarks, a good stopwatch, knowing about how fast you walk on average, and generally bisecting an area through canvasing. You could also try a mariner's astrolabe or a sextant (i think you can rig up one with an cd) and a map of the stars but you'd run into the longitude problem, but then you have your stopwatch, hopefully still.
You might also be able to google how to read your cell phone's built in gps if it has it for E911 service. I know my basic java based phone has a demo map program that even without buying it shows the coordinates.
The problem is some of the jerks really sneak the things into nooks and crannies, but mostly I don't think they do, and they give landmark descriptions of where the cache is. The civilian gps is only really accurate without after-the-fact calculations to within a few feet, so yeah, you could still have a lot of fun without a gps. But having one that saves your trail is rather handy and neat.