Low-level programming for embedded systems is quite different from programming for general purpose devices, such as computers and cell phones. Efficiency (in terms of speed and space) is far more important because resources are at a premium. That means the very first thing to do if you run out of space is to look at what parts of your code you can optimise.
In terms of reducing program space (Flash) usage, the code size can be quite difficult to optimise if you're inexperienced, or if you're more used to programming for desktop computers which don't tend to need that skill. Unfortunately, there's no 'magic bullet' approach which will work for all situations, although it helps if you consider seriously what your sketch really needs to have. If a feature isn't needed, take it out.
Sometimes it's also helpful to identify where multiple parts of your code are the same (or very similar). You may be able to condense them into reusable functions which can be called from multiple places. However, be aware that sometimes trying to make code too reusable actually ends up making it more verbose. It's a tricky balance to strike that tends to come with practice. Spending some time looking at how code changes affect the compiler output can help.
Runtime data (SRAM) optimisation tends to be a bit easier when you're used to it. A very common pitfall for beginner programmers is using too much global data. Anything declared at global scope will exist for the entire lifetime of the sketch, and that isn't always necessary. If a variable is only used inside one function, and it doesn't need to persist between calls, then make it a local variable. If a value needs to be shared between functions, consider if you can pass it as a parameter instead of making it global. That way you'll only use SRAM for those variables when you actually need it.
Another killer for SRAM usage is text processing (e.g. using the
String class). Generally speaking, you should avoid doing String operations if possible. They are massive memory hogs. For example, if you're outputting lots of text to serial, use multiple calls to
Serial.print() instead of using string concatenation. Also try to reduce the number of string literals in your code if possible.
Avoid recursion if possible as well. Each time a recursive call is made, it takes the stack a level deeper. Refactor your recursive functions to be iterative instead.
EEPROM is used for long-term storage of things that only change occasionally. If you need to use large lists or look-up tables of fixed data, then consider storing it in EEPROM in advance, and only pulling out what you need when necessary.
Obviously EEPROM is quite limited in size and speed though, and has a limited number of write cycles. It's not a great solution to data limitations, but it might be enough to ease the burden on Flash or SRAM. It's also quite possible to interface with similar external storage, such as an SD card.
If you've exhausted all other options, then expansion may be a possibility. Unfortunately, expanding Flash memory to increase program space isn't possible. However, it is possible to expand SRAM. This means you may be able to refactor your sketch to reduce code size at the expense of increasing data size.
Getting more SRAM is actually fairly straightforward. One option is to use one or more 23K256 chips. They are accessed via SPI, and there is the SpiRAM library to help you use them. Just beware that they operate at 3.3V not 5V!
If you're using the Mega, you could alternatively get SRAM expansion shields from Lagrangian Point or Rugged Circuits.