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.

Another way (other than MCU with more memory) is not using Arduino framework and its libraries. Such level of abstraction is expensive in both ways - memory usage and speed. But that's much harder way. If you need some library, you have to port it (if you haven't found native one) or at least provide required functions from Arduino.

For example in Arduino IDE 1.6.11 empty sketch is using up 444 Bytes of flash. Using one pinMode and digitalWrite(13, ! digitalRead(13)); + delay(500); means 964 Bytes. Of course, these are most likely one-timers. If you use six more pins and toggle it, it uses much less program memory than using first one (1192B). But it still grows really fast.

In pure C empty program is about 134 Bytes long. Same functionality (toggling one pin every 500ms) takes 158 Bytes (and it's way faster).

But for hobby project i would go for ATMega2560 or ATMega644/1284 instead.

And you can use direct access to hardware too. Toggle pin sketch with using registers directly and _delay_ms from avr libraries uses 468 Bytes instead of 964B. With delay from Arduino core libraries it's 602B.