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 distribute 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.
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.
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 miht be epigenetic but I don’t know the status of this theory.
With predator-prey patterns arose signals between organisms and soon thereafter incentives for deception. Some of this information was in the DNA but later also in the behavior encoded in the nerves.
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 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.