How would I go about getting a small oscillator running at precisely 31,891,269,116 µHz?

Use a 32768kHz crystal like everybody else, but divide by 33669 instead, giving -5.08ppm error. (You can remove that by trimming the loading capacitance if you like).

It's not precise but for a Mars clock it'll be as good as any Earth quartz clock. That is, ignoring the problems of temperature compensation for Mars ambient temperatures, most watch crystals are only available cut for Earth use, unless you can find Martian suppliers...

I'd use the counter-timer peripherals in an MSP430 to do the division, and (assuming you're driving a standard quartz mechanical clock movement) generate bipolar 30ms pulses on its output pins every second, roughly following the original timings which you can measure on an oscilloscope.

Arduino or similar will do the job, but the MSP can be put to sleep between pulses, consuming under 1uA with the LF oscillator running. Here's an example design with source code and PCB for a watch - only Earth time so far, though that can probably be fixed by changing a constant.

You can do better than Brian Drummond's suggestion. Although it may be true that your oscillator is the biggest source of error in the system, there's no reason to add additional systematic error when it's easy enough not to.

Set your timer interval to 33668 ticks, start a counter at 0, and on every timer interrupt, increment the counter by 6754.

If, after incrementing, the counter is >= 8105, then subtract 8105, and set the timer interval for the following second to 33669 ticks.

Otherwise, leave the counter alone and set the timer interval for the following second to 33668.

This will give you (assuming a perfect 32.768kHz crystal) an average interval of

(33668 + 6754 / 8105) / 32768 ~= 1.0274912510006

seconds (less than one part-per-trillion error relative to 1.0274912510), instead of 1.0274963378906 seconds (almost 5 part-per-million error). This means that the long-term accuracy of your clock will be truly dependent on the accuracy of the oscillator; the error due to the mathematics will contribute substantially less than one tick of error per year. Although the length of any single second will have a relative error up to 25ppm, over longer and longer averaging intervals the error disappears.

This is Bresenham's algorithm applied to timekeeping, and the fraction 6754/8105 was found as follows:

32768 * 1.027491251 = 33668.833312768

The exact continued fraction for 33668.833312768 is [33668; 1, 4, 1, 1349, 1, 7].

Dropping the last term gives the approximant 33668 + 6754 / 8105, which has all parts that fit neatly into 16 bits.

An Oscillator running at precisely 31,891,269,116 µhz or a timer with 1.0274912510 seconds period would require a precision of at least \$10^{-10}\$. Your best bet is to use an atomic clock which can be as precise as \$10^{-14}\$.