What is needed to store readable/writable data to flash/eeprom
Internal EEPROM

atmega8/attiny microcontrollers have up to 512 bytes internal EEPROM, if that's enough for your application, just use it. Otherwise, you might want to use the internal EEPROM for keys and pinters, and the external one for strings.

External EEPROM

They are commonly available in sizes up to 1 Mbit or maybe 2. Check the voltage requirements, decide the size and the interface.

Pick one from the Atmel AT24C series, they'll be most probably OK.

External Flash

If you'd need more than 256 kbyte, then it should be a serial flash, available up to 1 Gbit. There are more constraints here, as they usually have SPI only, no I2C. Supply and I/O voltage is in the 1.7V/3.3V range, if your ATmega is powered with 5V, you might get away with wiring MISO directly, and using simple voltage divider resistors for the oher lines.

For more than 1 Gbit, use a SD card, it can be accessed with SPI too.

Interface: I2C or SPI

I2C (sometimes called TWI) requires only 2 pins. You can connect more I2C devices to one bus, as long as they have different addresses.

Just connect SCL with SCL, SDA with SDA, add a pullup resistor to both of them, 1 kOhm for 3.3V, 1.6 kOhm for 5V. Configure them as open drain outputs. There are code examples in the atmel datasheets.

The protocol for accessing EEPROMS is dead simple, put the device address followed by the memory address and the actual data to write, or initiate an I2C read after the address bytes to read. Always check the returned NACK bit to see whether the memory is still busy storing the previous byte.

SPI

There are four lines: Clock, Chip Select, MISO (master in slave out) and MOSI (master out slave in). No pullups required, all 4 are unidirectional, MISO goes from memory to processor, the other 3 from processor to memory. The protocol is somewhat more complicated than I2C, especially for writing flash.