Most reagents are harvested as you continue throughout your adventure. Sometimes (about 25% or less) you will get a rare harvest from a common reagent. Acorns are harvested from mist wood, ancient scrolls are harvested from parchment, nightshade is harvested from deep mushrooms, etc. In the case of sandstone, it is found from harvesting stone blocks.
If you ever want to save time and spend a little extra gold, you can always go to the bazaar in wizard city. It depends on the day, but most of the time, reagents can always be purchased there. Be careful though. Many "rare harvest" reagents buy for at least 100 gold.
Fossil is a rare harvest, which means no vendors sell it. However, you can occasionally find fossil at the bazaar, or you can buy the transmute recipe (turn 15 stone block to 1 fossil) from these vendors for 200 gold: Balthazar Dragonthorn in The Atheneum, Dragonspyre Avery Templeton in Celestia Base Camp, Celestia Kimba Kalla in Water-Mole Village, The Floating Land, Celestia
Please note that Initiate Crafter is required to transmute this. You need to transmute fossil with the Card Crafting Station.