A discussion about gorgons led to the question “just what kind of stone do gorgon’s victims get turned into?”. Since that is not factually answerable the next best thing would be actual fossilization; what type of stone are fossils made out of? Is there usually a difference between marine and non-marine fossils, or what other qualifiers might apply?
Quite a lot of ‘it depends’ here.
Fossils that are preserved by infiltration of minerals (where there is still some of the original bone or shell etc present in the fossil) are often preserved by silicates, but that can manifest as a number of different actual minerals, like chert or other clear or opaque forms of quartz or opal. It can also be calcium based minerals such as calcite or limestone (limestone itself is made from fossils anyway)
Other types of fossil are formed when the organism is buried and the matrix solidifies, then the organism decays leaving a cavity that fills up with other minerals. This can be a variety of different things. Pyrite is common, but so are silicate and carbonate minerals.
For fossils of some marine organisms, what is preserved may just be the remnants of their bodies, pressed flat in between layers of sedimentary rock. The weird creatures in the Burgess Shale, for example are I think made primarily from carbon from the body of the original organism.
Regarding the stone that Medusa’s victims were turned into – aside from the statement that her victims were turned to stone, we have precious little to guide us in determining this. Most of her victims are not mentioned. Those gardens of stone statues surrounding Medusa’s lair don’t appear in ancient myth – they’re mainly in modern movies, like both versions of Clash of the Titans or the Italian Perseo l"Invincible or the first Percy Jackson movie, The Lightning Thief.
One of the few victims we know about is the sea monster Cetus (Ketos). Later myth has Perseus turning the monster into stone with the gorgon’s head (as depicted in both versions of Clash of the Titans, which both give Cetus the Scandinavian name of “Kraken”). In earlier versions of the myth, I point out, he didn’t do this – he killed the monster with his harpe (his characteristic curved sword), or in the earliest graphic depiction we have, throwing rocks at it.
But in one later version, the town that was threatened was Joppa – modern-day Jaffa in Lebanon – and there is a rock in the harbor called “Andromeda’s Rock”., which is either the rock she was chained to or the remains of the petrified Cetus. Even if the rock isn’t Cetus, the nearby rocks would have to be the petrified remains. I’ve been trying to learn what the blackened rock is composed of, and it appears to be a sort of sedimentary rock
Another feature said to be the petrified remnant is the isle of Pontokonsi, said to be the ship of the Phaeacians, who returned Odysseus to his home in Ithaca, thius incurring the wrath of Poseidon (who hated Odysseus), who turned the ship to stone and blocked the harbor.
I haven’t been able to learn the geology of the island, but I suspect that, in every case of petrification, the thing turned to stone has been turned into whatever the local stone is.
Jaffa is not in Lebanon…
Apologies.
Israel
No, since the petrification usually happens well after the sediments have lithified and so aren’t really related to the deposition environment. What matters way more is the composition of the surrounding rock, as that’s going to determine whether it’s a silica gel, a carbonate solution or something exotic like pyrite or haematite that does the replacement/permineralization.
Silica is the most common, but that may be a preservation thing too as carbonate replacements may get dissolved.
If I were DMing a petrification effect, though, it would have to be marble, as unlikely as that actually is IRL.
“Opal-like” is close enough for me.
Hi Opal!
Never mind, old joke.
It’s interesting that opal and mother-of-pearl both achieve their iridescent colours by the same general principle (microscopic structures interfering with light), but they do it using different chemistries and different structures - Opal is composed of microscopic spheres of silica that are arranged in pseudocrystal lattices; mother-of-pearl is composed of microscopic hexagonal plates of aragonite (calcium carbonate) that are stacked in laminated arrangment.
There are such things as opalised fossil seashells (where opal is the mineral that infiltrates the fossil and preserves it.) I wonder if there are any examples where the nacre of the shell is preserved (like ammolite) and also retains its iridescence, right alongside the opal…
For D&D-style petrification, I assume that different kinds of tissue get turned into different kinds of rock (and vice-versa). That’s why a Stone to Flesh spell will get you a working body again, instead of just a body-shaped pile of random meat.
Now I have a hilarious image of fantasy geologists classifying different types of minerals as “liverstone”, “kidneyite”, and so forth. 
Mudfossil University does that, in the same world as we live in.
One of the few fossils I’ve personally found was a plant fossil in coal; it was made from golden pyrite. That would be a colourful stone to be turned into.
A bit deceptive perhaps, which is why they call it fool’s gold.