If you record time + date with your sample, it is not necessary to take equally spaced samples. you could sample at a slow rate, but when there's some big variations measured, increase the sample rate.

Or as HenrikOlsson said save memory by storing only the fist time/date tag, but then you have to keep the same sample rate. This is the solution I'm implementing currently in my USB temperature logging jumpdrive.

Here is the table I generated, considering an header of 40 bytes in EEPROM, followed by individual 12bits temperature samples (I use a TMP100 sensor which output celsius values at 11bits + sign).