This is something that I sometimes think about since a long time: What would be the best way to store "data" over thousands of years, maybe even a million years?

DNA is an obvious candidate, but on the "macro" level, how about mating rituals??

Birdsong, or the elaborate shapes that some fish draw in the sand of the sea floor. The species HAS to pass them on in order to reproduce.