Simple memory chip for Arduino?
There is no DRAM, SRAM nor flash interface in ATmega, so you can't extend your chip memory. You can only connect serial (SPI, I2C) or parallel memory (usind GPIO).

Neither SPI nor I2C require any specific libraries.
SPI is much simpler to program than I2C and much faster, but require more wires.

Instead of using rather slow EEPROM, you can try FRAM (non-volatile) or SRAM (volatile, but may be battery-sustained). They are usually available with the same interface as EEPROM, but don't suffer from limited number of erase cycles. FRAM can withstand ridiculous number of erasures, SRAM is virtually indestructible.