I don’t think the methods were worked out as much as evolved with the human brain. I suspect those who started using mnemonics survived and bred better than those who didn’t.
I have been pointed to this discovery of a Neanderthal cave many times, with archaeologists suggesting to me that it points to Neanderthal use of a memory palace. It would need more evidence to be convincing, but that would go back a very long time.