How to design a device that can retain data for more than 20 years?

[amyk]

Flash memory trends tend to be at odds with longevity, increasing densities require smaller feature sizes and that means fewer trapped electrons, thinner gate oxides, and so less program/erase cycles and shorter data retention times. If you really want data to last, write it physically (e.g. pressed CD, DVD) or maybe magnetically with appropriate shielding.

[minibutmany]

Encode it into audio and put it on vinyl.

[Stonent]

Stone works, that's why we still remember the 15...er 10...10 commandments!

[poorchava]

If keeping the data is critical place two flash chips in the circuit both containing the same data and a hash or checksum of it. If one of them fails then inform the user to replace it with blank chip and copy contents of the remaining one.

[notsob]

We'll someone had to throw this into the mix  Write-Only memory

http://www.repeater-builder.com/humor/signetics-wom.pdf

Data retention is not a problem

[Whuffo]

NOR flash is probably the sweet spot in terms of reliability vs. cost. AFAIK there aren't any block issues Avoid any packaged devices like SD cards as their internal ECC will hide any errors until the point where they are suddenly unreadable.
If you implement your own ECC, you can detect and deal with errors before you lose data.
With  any periodic rewrite system you need to be careful about how you implement and test it, in particular dealing with loss of power, both from the point of view of keeping track of  rewrite intervals, and errors caused by power loss during write.

And of course don't forget to keep in mind the reliability of the flash your code is running from.

Great advice. I'd just add that you'll want to shield those memories very well; long term storage is often compromised by the stray cosmic ray zipping through and flipping a bit or two. Ionizing radiation of almost any frequency will interact with the memory cells in unexpected and unwanted ways.