How to program external EEPROM using USBtinyISP or Pocket AVR programmer

Please check page 15 through 18 of the datasheet. You'll find some Diagrams which explain the procedures involved quite good. Also there are timing diagrams on page 12 and 13.

For example, to erase the chip you have to do the following:

1. Set A9 and OE#/VPP to 12V
2. Hold CE# low for at least 100ms
3. Remove 12V from A9 and OE#/VPP
4. Wait a moment (1µs)
5. Check all addresses for 0xFF (If this fails, there was some problem with the erase operation)

For programming you do the following:

1. Set OE#/VPP to 12V
2. Set Byte Address on A0-A15
3. Set data on D0-D7
4. Pulse CE# low for 20µs
5. Go back to 2. for more data
6. Remove 12V from OE#/VPP
7. Wait a moment (1µs)
8. Check all written data

Yes, an EEPROM is a type of nonvolatile memory which can hold data even without any power for a significant amount of time (the actual time depends on temperature and other conditions).

There are a few other non volatile solutions for you to consider:

1) Internal Flash memory - Most microcontrollers nowdays have Flash for code storage and some provide it for user data and logging as well. This also has limited write cycles and requires block erase before changing bits from '1' to '0' (you store data elsewhere in the meantime and then rewrite it).

2) Internal FRAM memory - TI has devices with FRAM memory which is nonvolatile, can be accessed very simply (like any other memory location. Reads are also destructive as writes (though in your case this might not matter since the number of cycles is 10^13 or so at 85 degrees celsius).

3) External Flash memory - You can add memory externally to hold a few megabits of data rather inexpensively.

Depending on the rate at which you want to save (and whether you can shutdown nicely) you might be able to increase the effective number of cycles available for you.