The word Fossil comes from the Latin word fossilis, which means "dug up." Most fossils are found in a Sedimentary Rock called Sandstone.
Sedimentary rock is rock that has formed from sediment, like sand, mud, and small pieces of rocks, plants, and animals.
Over long periods of time, these small pieces are compacted as they are buried under more and more layers of sediment that pile up on top of it. Eventually, the sediments are compressed and cemented into sedimentary rock. The cementing occurs when mineral rich water flows between the individual sediments. The water leaves behind the minerals that form crystals and bond ("glue') all the sediments together.
A fossil can form when a dinosaur dies and gets quickly buried in sediments. The soft tissues rot away leaving only bones. Over time through compacting and cementing, the material that makes up the bones gets replaced by minerals until only rock in the shape of the bones remain.
Layers of Sedimentary Rock that are farther down in the Earth contain fossils that are older than fossils found in layers above.