Is there any way to store variables that will persist even after a full power cycle?
I am wanting to store a counter, and keep it - even if the power cycles.
You can store it in EEPROM memory:
However, if your counter is being updated rapidly and often, you only have a limited number of write-cycles on the EEPROM (something like 1,000,000 cycles on average, IIRC - the ATMega datasheet has the exact average number). Keep that in mind...
Thanks, I just looked up the numbers:
Write/Erase Cycles: 10,000 Flash/100,000 EEPROM
So, looks like I only have about 10,000 writes?
So, looks like I only have about 10,000 writes?
No the advice was to use EEPROM that's 100,000 writes. The trick is not to use them up all at once.
I might get the 24LC256, it seems to be easy enough to interface too, and very cheap also.
And has the same sort ow write cycle limitation, all non volatile storage has.
Seems a little less destructive if I use an external though right! 
Why is it limited? Does the magnet (or however it stored) wear out, or is there some non-reset-able timer?
Basically it wears out, capacitive dielectric actually.
The primary wear out mechanism is believed to be excess charge trapped in the oxide of a memory cell and the net effect is that erase times increase until.....
Well, I suppose if I write to it once per hour, that's like 10 years, so I suppose its not so bad. Something else would probably break or wear out before that would be gone.
(100,000 / 24 / 365 = ~10.5 years)
Yes that is the way it should be used, only occasional writes. Also that is per memory location, if you spread things out they all last that long. It is not the writing that kills them it is the erasing. An erase cycle will set a byte to all ones, you can write zeros to each individual bit so that's 8 writes for one erase so you might want to arrange things to take advantage of those two techniques.