First of all, was that a Heinlein reference? My copy of Tunnel in the Sky is on loan right now.
Second, what resources do you have available? Extensive reference books? An appropriately-programmed computer? A telescope, and if so, what size? Can you get above the atmosphere, or take non-visible observations? How long are you willing to observe?
In the best case, start by getting above the atmosphere and measure the temperature of the cosmic microwave background. This will get you to within a precision of about a million years all by itself. No, that’s not very precise, but it’s an important start, because it’s not periodic at all: you can’t possibly be off by more than that approximately million years, from being in a different cycle than you think. It’ll also work at any point in time in the Universe’s history, until the CMB redshifts so far that it’s not detectable at all.
Now we need to start looking at periodic phenomena. Ideally, we’d find something with a period not much longer than the timespan we’ve just narrowed down to. Unfortunately, the best I can find are the period of the Sun’s orbit around the center of the Galaxy (225 million years), and the period of the Earth’s precession (26,000 years). So, OK, let’s work with that. To measure where the Sun is in its orbital cycle, you’d want to measure the angle between the center of the Andromeda galaxy (visible even to the naked eye) and SagA*, the center of our Galaxy (easily found using any radio telescope at all). You could probably measure this angle to within an arcsecond, if you’re above the atmosphere and have good instruments, but I don’t think that the Sun’s ephemeris is well-enough known to take advantage of that. Rough back-of-the-envelope, it’s probably going to be a bit worse than what we already have from the CMB. So it’ll let us confirm what we already have, but that’s not good enough.
So, on to the precession of the Earth. With a cycle length of 26,000 years, and a million-year window, we’re going to have about 40 possible solutions. But we’re not sunk: All we need is another cycle of comparable but different length from the Earth’s procession, and we can compare the phases of the two cycles. And fortunately, we have one: The perihelion precession of Mercury has a period of about 22,000 years (though it’ll take time to measure it). Note, by the way, that this is not the 43 arcseconds-per-century precession due to general relativity: The total is 5600 per century, with the rest accounted for by Newtonian sources. By comparing the two cycles, we can easily pin ourselves down to one precession-cycle, and to one portion of that cycle.
How small a portion? Well, I’m not sure offhand which one of the two we can measure more precisely, but if you’ve got the time to do the perihelion-of-Mercury measurement, you can certainly measure it to within one part in a few thousand (since the scientists of Einstein’s time were able to do so, to notice the 43 arcseconds-per-century discrepancy). So now we’re down to a window of mere tens of years.
From here, we’re sitting in butter. With a window of tens of years, the orbit of Jupiter, Saturn, Uranus, or Neptune would any one of them be enough to pin it down, certainly to the year, and even more certainly if you had all four of them. And once you have a one-year precision, the familiar cycles of the Earth itself will easily get you to a day, and if you know your longitude, to a minute or second.
Of course, that was all assuming the best-case scenario. Take away some of the advantages I used (above-the-atmosphere, microwave detection, and long observation times), and we’d have to see what else we can come up with.
EDIT: That post took a while to write-- There were no responses when I started.