Two approaches that I use,first is to use an eeprom as suggested,usually with some form of data compression.The second is non-volatile SRAM which has some form of battery back-up to keep it running in low power mode when the main power is switched off,Try Dallas semiconductor they do several sizes of non-volatile memory.and some 64Kbit serial eeproms.
Jez