Materia is basically congealed memories. When you die, your soul goes into the Planet as spirit energy, and all of the different parts of you split away and flow in the currents of the Lifestream. When your memories of fire meet someone else's memories of fire, they flock together. As they gather, they coalesce, tighter and tighter, like a school of fish, and then as one unified section of Lifestream. Then they get snagged on something and create a mako fountain, which produces materia.
Going by this logic, we can assume that the more memories there are, the more abundant that materia will be. We can also assume that if enough people were to imagine the same thing (Shiva, for example) then that imagining - the memories of that imagining - would congeal and become real (this is my explanation for summon materia).
My thinking is that the black materia was made from the fear of death.
You could be more specific and say that it's their combined imaginations of a giant meteor, based on their experiences with Jenova's arrival (there's a goddamn crater where she landed. Big momma) or other somesuch, but I think death-by-a-giant-meteor is a pretty common fear to have. Hell, didn't Armageddon and Deep Impact come out within months of each other? It's not unlikely that a meteor wiped out those giant creatures that you find near the Planetcore, and it isn't unlikely that the Cetra knew about it, what with their Planet-readings and stuff.
I'm hesitant to believe that the Golden Hall in the Temple of the Ancients is depicting things that have happened in the past. I think it's more or less a warning label. I figure that the Cetra discovered how materia was made, and were like "Ho shit! There's probably an Armageddon materia, it's probably that sinister looking one over there! Let's hide it and warn people with pictures so you don't end the world if you can't read."
I also imagine that the Temple kind of draws in any new memories about the rapture or whatever and hides them. This is mostly speculation, because the Cetra weren't too into building ziggurats. Actually, most of this post is a big educated guess, but it's the clearest explanation I can find.
tl;dr - dead people's dark thought soup.