Sometimes I run out of space of the program size for the embedded C program that I want to put on an arduino. So what chip do I need to expand the program memory of the arduino so that I can use bigger C programs with my 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
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.
Wen asking a broad question, it is helpful to include some details. Like how much memory and why you think you need it.
I once specified a processor at 2 KB program space, 64 bytes RAM and 1 KIPS. The engineer asked, MIPS, I explained thousands per second. He replied, they don't come that slow. At the end of the project, a huge UI was added and memory got tight... but still fit with no problem.
So, consider being more thoughtful about the resources being used.
To answer the question:
1) The Arduino does not provide a convenient bus to fetch memory over. So, there is no way to plug in a chip to get more memory.
2) The Arduino has SPI, so an SD card can be accessed. Any code on the SD card would need to be loaded into executable memory. This is complicated and not for beginners...
3) As suggested, tighten up you code. This is probably a good way to learn.
3) Move to a larger Arduino.
There are different Arduino processors. Some in the ACR line, others in the ARM line. Going to a different device in the same family is a relatively modest change and can provide up to 368 Bytes of progam FLASH. But these are not Arduino boards exactly.
The Arduino ARM based devices are very differnt and use different libraries.
Check out the Arduino Mega 2560 it is very similar to the Uno, has a similar footprint, code should port relatively easily and is inexpensive.
There are larger devices in the AVR family.
Note, the AVR32 is a different processor and the peripherals are enough different that it is a different device.
If you want to get into very large programs (gigabytes of memory) check out the Beagleboard. It has a full linux, with virtual memory (see #2 above) and has more powerful I/O mechanisms.
What about a raspberry pi zero? I have a couple and use them quite often as arduinos.