Flash memory, like EEPROM, stores its information in so-called floating gates. Normal gates on (MOS)FETs have an external connection through which the FET is switched on and off (for integrated MOSFETs this would be a metal layer connection). Floating gates don't have this pin or metal layer connection. They sit completely insulated in SiO\$_2\$ above the MOSFET's channel, and at > \$10^{14} \Omega\$cm SiO\$_2\$ is one of the best insulators you can get.
Like traditional MOSFETs they switch the channel on when they carry a charge. But how are they programmed then? Through a quantum effect called tunneling which is induced by applying an electric field between the channel and a control gate. The technology is therefore called FLOTOX, short for "FLOating-gate Tunnel OXide", comparable to FAMOS ("Floating-gate Avalanche injection Metal Oxide Semiconductor") used in the older UV-erasable EPROMs.
(I can't explain tunneling in detail here; quantum effects defy any logic. Anyway it relies heavily on statistics).
Your first question is actually a double one: 1) can I perform unlimited reads and writes, and 2) does it retain the data when the device isn't used (shelf life)?
To start with the first: no you can't. You can read it an unlimited number of times, but write cycles are limited. The datasheet says 10 000 times. The limited number of cycles is caused by charge carriers left in the floating gate after erasure, whose number in the end becomes so large that the cell can't be erased anymore.
Will it retain its data for 20 years even without power? Yes, that's what the datasheet says. MTTF (Mean Time To Failure) calculations (again a statistical method) predict less than 1 part per million errors. That's what the ppm means.
a note on MTTF
MTTF means Mean Time To Failure, which is different from MTBF (Mean Time Between Failures). MTBF = MTTF + MTTR (Mean Time To Repair). Makes sense.
People often use the term MTBF when they actually mean MTTF. In many situations there's not much difference, like when the MTTF is 10 years, and the MTTR is 2 hours. But failed microcontrollers aren't repaired, they are replaced, so neither MTTR nor MTBF means anything here.
Atmel quotes 1ppm errors after 100 years. It's obvious that the AVR hasn't been in production for that long, so how would they come to that figure? There's a persistent misunderstanding that this would be simply a linear thing: 1 defective device after 1000 000 hours would be the same as 1 defective device per 1000 hours in a population of 1000 devices. 1000 x 1000 = 1000 000, right? That's not how it works! It isn't linear. You can perfectly have errors after 1 million hours, and none after a thousand, even with a population of a million! MTTF calculations take all kinds of effects into account that may influence the product's reliability, and attaches a time for each of them. Statistical methods are then used to come to a prediction when the product will eventually fail. See also "bathtub curve".
(Forget the Wikipedia errorticle on MTBF. It's wrong.)
How does it lose its data? The gate charge will not leak away in the same sense current leaks in normal circuit through high resistances. It will do so the same way it's programmed and erased, through tunneling. The higher the temperature, the higher the energy of the charge carriers and the bigger the chance that they tunnel through the SiO\$_2\$ layer.
Federico's question if the 1 ppm refers to devices or cells is justified. The datasheet doesn't say, but I presume it's 1 defective data cell per million. Why? If it was devices you would get worse figures for devices with bigger Flash sizes, and they're the same for 1k as for 16k. Also, 100 years is extremely long. I would be surprised to see 999 999 devices out of 1 million still working.
images shamelessly stolen here