Genetic drift may capture useful information on time scales of dozens of generations. It is in the DNA (nowadays) but does not require new genes in the DNA or even the discovery of new SNPs—merely the current advantage of some genetic potential.
Epigenetics may have developed concurrently, or may have been a later evolutionary phase. Epigenetic information has a duration typical of the lifetime of an organism.
With multicellular organisms arose a strategy of reacting in this cell to an external stimulus to another cell. Nerves could sense, compute and transmit signals for action in order to implement these strategies. Such strategies are coded in the DNA but transferred to the nerves during morphogenesis. The behavior was in the genes and nerves, but the state was only in the nerves—a read only program. The nerves both processed and transmitted information.
This stage is like the simplest of control systems with one cpu and a few bytes of RW memory and a few kilo bytes of RO memory.
Some of these strategies would benefit from information storage of state with different time scales. I imagine scales from seconds to organism life-times. I doubt that one technology can serve greatly different time scales and that several storage technologies must be separately evolved. Control system engineers find this to be the case.
Much later an organism could learn in its life time; this learning required the nerves to have access to long term information that was not available in the DNA. Some have speculated that such information might be epigenetic but I don’t know the status of this theory. See Long-term potentiation.
With predator-prey patterns arose signals between organisms and soon thereafter incentives for deception. Initially this information was in the DNA and thus permanentely encoded in the nerves, and later patterns acquired in the lifetime of the organism.
Perhaps olfactory and visual sense organs resulted mainly from an arms race in the predator-prey game. In any case they gave rise to heavy computing demand, as well as muscles with which to move about. Brains would begin to result from consolidation of nervous activity for convenience of communications. Information storage would continue the strategies mentioned above for storage on different time-scales.
Very gradually the state part of these evolved behaviors would begin to model the nearby world outside the organism. Multiple specialized instantiations of behavior, each with its own learned state, seems likely.
Evolution is always on the lookout for useful sources of information—sources that provide survival advantages. The brain itself is such a source in a sense that I think has been largely overlooked. I believe that this can explain much of what we call consciousness.
This is not much good as a theory for producing predictions. I do predict that there are several different evolved information storage mechanisms in the human brain for different time scales—perhaps three or four.
Some good stuff that I found after I wrote the above.