A fossil is any trace of past life. Many fossils are bones, shells, or other body parts, but fossils do not have to be actual pieces of ancient organisms. However footprints and other traces are fossils too. Trace fossils include thin crinkly layers of sediment trapped by ancient algae, grooves cut in sand by the movement of wind-tossed plants, tail-dragging marks, worm trails or burrows, and many more. Even organic chemicals can be fossils, if they record the former presence of organisms.
To be preserved as a fossil, an organism's remains must essentially be removed from the biosphere. This usually means rapid burial in an environment that contains little or no oxygen. This could be in a black lake mud, in tree resin (amber), or simply in an unusually thick sand bed deposited offshore during a hurricane. The chances of preservation are best in fine-grained material such as mud, which not only excludes air but also slows down the movement of ground water, preventing the fossils from being dissolved. Exposure to water and oxygen quickly degrades fossils, so for organic remains to be fossilized they must somehow be protected from these two agents.
The important thing to remember is that most organisms are not preserved as fossils, but are recycled into the global cycles of carbon, nitrogen, silica, phosphate, and other elements and chemicals important to life. The soft tissues of plants and animals are rapidly broken down after death by molds, bacteria, and scavengers. The skeletal parts (which paleontologists like to call the "hard parts") last longer and therefore have a greater chance of being fossilized. But even most teeth and bones seldom last more than a few years when exposed to the elements, and their atoms are recycled into the biosphere and reused.
Hard parts can be composed of organic or inorganic materials. The organic materials, cellulose, lignin, and chitin, are the most susceptible to decomposition, so plants and insects are rarer as fossils than seashells. Many shells are made of calcium carbonate, which comes in two mineral forms, calcite and aragonite. Calcite is generally more stable than aragonite at the earth's surface, and it is common to see a fossil bed with the calcitic shells well preserved and the aragonitic shells dissolved away, leaving only molds. (This is very common in the Cretaceous chalks of Alabama.) The skeletons of organisms may be numerous enough to dominate a sediment. Almost all limestone is made up of fossils, as are coal, diatomite, and some chert and phosphate. Even a limestone that doesn't seem to contain any fossils when examined with the naked eye commonly turns out to be made up of microscopic fossils, some visible only with a powerful microscope. Most fossils are microscopic shells consisting of silica (the material in glass) or calcium carbonate (lime).