There’s a great article in the January 2003 CACM which describes some very long-term data storage technology (Organic Data Memory using the DNA Approach).
In a nutshell, you encode your information using sequences of DNA base triplets (AAA, AAC, AAG, and so on), then splice these on to the end of a DNA strand, making sure that the stuff you write is past that strand’s stop codon. You then perform the necessary magic to get this DNA into the host’s genome. That way the new material will not take part in protein synthesis, but will be passed down as genetic material from generation to generation.
This isn’t science fiction: the researches encoded the words of “It’s a Small World”, added them to a bateria’s genome, then extracted the information again. Because bacteria can withstand all kinds of abuse (dessication, extremes of temperature, and so on), they believe that this gives us a good long-term storage scheme. (There’s the problem of mutations to deal with, but decent error correcting codes could probably deal with this).
Now, of course, we’ll see the RIAA step in to the act and insist that they need to add unique digital signatures into every human being.