How to expand program memory on an arduino?
An ATmega2560 is the chip to add for more memory when you run out of program memory on an Uno.  Referring to the Memory webpage at arduino.cc, you'll see that it has Flash=256KB, SRAM=8KB, EEPROM=4KB, where the ATmega328 chip on the Uno has Flash=32KB, SRAM=2KB, EEPROM=1KB.

When you run out of program memory on an Uno, you have about three choices that are practical:  make the program smaller; remove the bootloader (to free up one or two KB); use a different board with a more-capable processor.  The CPU on an Uno board doesn't have a way to access program bytes from places other than the on-chip 32KB flash.  The CPU on a Mega2560 board starts out with 8 times as much flash, so it can hold bigger programs than an Uno can.

If you remove the bootloader, you could instead program using a USBASP board, as described in a 
“Program AVR chip using a USBASP with 10 pin cable” article at learningaboutelectronics.com.