Arduino database

Jikdor:
The first thing that comes to my mind is the internal EEPROM

I'm pretty sure the first thing that would come to anybody else's mind is an SD card. You can get a module or about $2, and they are not hard to use.