The common ancestor of mollusks, arthropods and chordates (sea snail, fruit fly and mouse) was about 530 million years ago. Bjorn Brembs posts on two learning systems that appear to be this old. (here)
Synaptic plasticity which changes the connectivity between neurons seems to have two different chemical routes: (1) neural transmitter, rutabaga adenylyl cyclase, cAMP, PKA, CREB, DNA to give long-term memory (2) similar but a different cyclase enzyme instead of rutabaga, PKC instead of PKA, FoxP instead of CREB.
The two chemical routes can be separated by either a PKC inhibitor or interfering with the FoxP gene. The research has been done on the sea snail, fruit fly and mouse. By killing the PKC route it appears that the PKA route is likely to be used for classical conditioning which relies on external cues and is thought similar to declarative memory. And it appears that the PKC route is likely to be used for operant conditioning which relies on self motion and is thought similar to procedural memory.
If this turns out to be confirmed, it would mean that our two basic memory systems are as distinct as they appear and are very old indeed. It is interesting that the FoxP gene is involved procedural memory this is a gene that in humans and song birds appears to help facilitate learning language and song. Also interesting is that there may be a link between classic conditioning and declarative (passing through consciousness) memory.