Most of the earth's surface is covered in a type of rock called sedimentary, because it forms from layers of sediment building on top of each other. One of the characteristic features of sedimentary rocks is the high amount of fossils that they contain. All sorts of extinct plants and animals are preserved in sand, silt, or mud from ages long past.
Over time, animal corpses on sedimentary rock surfaces are covered by silt. The bones undergo mineralization, whereby minerals replace the original organics to leave a cast of the organism. Over great lengths of time, the organism becomes entirely replaced by durable minerals. In the petrification of wood, the cellulose and woody fibers are replaced by minerals such as silica.
Even delicate features are sometimes preserved in fossils. The eyes of flies and the delicate wings of butterflies have been found preserved in fossils. The majority of fossils, though, are thick shells or skeletons. Animals with lasting fossils are also some of the most widely studied and understood.
It is surprising that something as soft and subtle as sand can turn into something as rigid as a fossil. The reason is in the pressurization that sediments undergo as they are buried further and further. For every 100 feet (31 meters) of depth, average temperature increases by about 1°C. Average pressure increases about 1 ppsi (pound per square inch), or about 7 kilopascals, for each foot (31 centimeters) of depth. The increased pressure and temperature leads to a process called compaction, whereby the delicate particles in sediment are closely worked into each other and become rock.
Mud is purified of water during the process of compaction, becoming rock. Sometimes the increased heat leads the material to undergo chemical transformations, called cementation, which causes minerals such as calcite, silica, and iron oxide to build up films on the surface of the sediment. This is how fossils are made. The minerals also occupy air pockets between the sand molecules.
Fossils can also preserve things other than actual bodies. Footprints, tracks, trails, and burrows have been found. Since coal itself is compacted vegetation, many fossils can be found within it.