Just slapping a random capacitor across your supply is not going to work. It's far more complex than that.
Yes, a capacitor is used to store a charge, but you have to manage that charge properly or you won't get much of a chance to do anything with it.
You need to:
- Ensure that the discharge voltage remains high enough to run the chip for long enough to save your data (Note: writing to EEPROM causes an increase in current)
- Isolate the capacitor from the rest of the circuit so it only powers the main chip
- Monitor the incoming power to know when to do the saving.
A block-diagram of your setup may look something like this:
simulate this circuit – Schematic created using CircuitLab
In that diagram R1 and R2 form a voltage divider so you can monitor the battery voltage. C1 is a big capacitor. We're talking super-cap teritory here. Rated at 9V minimum. The regulator on the Arduino is ignored. You don't want to use it. Two external regulators are now used to power your project - one direct from the battery to run the breadboard and other external components (which will lose power immediately the battery power is removed) and the other to run the main MCU and nothing else. The second regulator is isolated from the rest of the circuit by D1, and the capacitor's charge then can only go through that regulator to power the main MCU.
That regulator for the MCU should be a switching regulator (DC-DC, "buck" regulator). If you use a linear ("LDO") regulator you will waste power and your capacitor will have to be two or three times bigger than otherwise. Even better would be to have a "buck-boost" regulator that will boost the voltage up to 5V when the input voltage drops below 5V, thus giving you even more life from the capacitor.
An alternative to all this is to use the 47C16 chip (5V) or 47L16 chip (3.3V) to store your data. This is an "EERAM" chip - an EEPROM with RAM buffer and automatic saving to EEPROM at power failure. It works through I2C and needs a capacitor connected to it directly to provide the backup power while it stores the data to EEPROM.