Easiest way to add more memory?

What is the easiest way to add more memory to an Arduino Duemilanove (above the 512 bytes EEPROM available)?

Change the 168 processor for a 328.

If you are talking about EEPROM memory (i.e. non-volatile), you can add an external EEPROM chip.

http://www.arduino.cc/playground/Code/I2CEEPROM