Writing to a microcontrollers internal EEPROM may be the easiest of all. See
here if you want
really simple. Alternatively if you are using assembly or C, these can also write to the internal EEPROM on an AVR (and other microcontrollers). If you are looking for something external, there are external flash chips. One external method I am considering trying is MRAM, non-volatile RAM with infinite cycling, see here for a parallel interface, you can also find SPI chips on their site.
I hope this helps,