Today, there are fossils of many animals. But how were they formed, let alone how they stayed till today?

For many years ( many millions of years ), life was marine for all organisms, and the oldest fossils are of marine animals ( though there are many fossils of land animals, they came later). When an animal died, it's remains went with it. The flesh was generally eaten, and the bones left behind . Not only bones, but shells and skeletons of calcium known as exoskeleton and endoskeleton, depending if they were on the inside or the outside of the animal, remained. This was covered up by a flood, sand or ash ( from volcano's ) and they were preserved under them. Of course, none of the material deposited was airtight. There were pores, into which water passed, with dissolved minerals. Over millions of years, they dissolve and a mineral replacement is formed, that is hard. These were embedded in the rock ( sometimes though, the bones were hardened by the minerals ). The bones are said to be petrified or turned to stone.

Fossils need not be only in mud, they have been found in tree sap ( insect bodies ), ice casing ( mammoths, that are so beatufully preserved, that there is even hair ) and many other material.

Soetimes, the animal decayed, but there was a mould in the sand, that was hardened by minerals. Footprints have been found.