A fossil is the preserved remains, impressions or traces, through natural circumstances, of an organism.
Preserved bones, leaves, feces, eggs, shells, skin, footprints, etc. are examples of fossils. Scientists love them because they can figure out how living organisms used to be, date them with radiometric testing and stratigraphy, put them in museums, sell them to collectors, and other neat stuff. Fossil collecting is a hobby engaged in by many passionate, slightly crazed amateurs.
To be considered a fossil, the remains have to be older than about 10,000 years, or longer ago than the end of the last Pleistocene glacial event. 
There are three broad types of fossils - ones composed of the actual material the original creature was composed of, ones where the original material has been replaced by some mineral after the original material completely decayed or dissolved, and ichnofossils, which aren't of an organism at all but instead preserve a marking left by an organism (e.g. footprints, trails, fossilised dung).
Fossils consisting of the original material are typically preserved by entrapment of a dead or living creature in peat bogs, tar pits, ice, or amber, all of which are capable of preserving at least some organic tissues for many thousands of years.
Fossils that are mineralized go through a more complex process. A typical "positive" cast is formed when the organism's remains are deposited in a bed of sediment. Over time, the sediment will be compressed and form into rocks such as sandstones, shales, or limestones. If conditions are right, when the sediment is stable enough not to collapse, but still porous to percolating acids and alkalis, the organism's remains will be dissolved away, but the shape will be preserved. Then, later percolations may deposit minerals in the cavity until they fill it completely. The deposited mineral will then form a positive cast. The surrounding bed of rock might also preserve a negative cast.
In the example of the mollusc pictured below, the fossil we see probably formed after the flesh was dissolved, but the shell was still trapped in the rock. Minerals filled the shell and solidified, and later the shell dissolved but was not replaced with any lasting deposits.
Mineralized fossils are not only typically much older than "preserved" tissue due to the time it takes to form them, but are then also much more stable and can endure for millions of years.
On a geological time-scale most biological material is ephemeral. It requires special conditions for material to be preserved for any length of time and then covered up by sediments. Anti-evolutionists like to point to gaps in the fossil record as major flaws in the theory when the reality is that it is amazing we find any fossils at all.
 Fossil pictures
 Fossil dating
Generally, fossils are "dated" by analyzing the rock formations in which they are found (since the minerals in a fossil itself may be much younger). Fossils first appear in large numbers in rocks dating from the “Cambrian explosion”. According to radiometric dating, this era was roughly 550 to 490 million years ago. Young earth creationists twist science and logic into ugly knots trying to find fault with radiometric dating. Some fossils date from even earlier than the Cambrian.
 Fossil fuel
Fossil fuels are so named because they are the long term result of deposition, decay, burial, compression, heating and chemical alteration of plant material laid down over a very long period of time. The carbon in these deposits originated on the surface of the earth as living plants. The bamboo and leaves pictured above are embedded in shale, a sedimentary rock often found in close proximity to coal deposits (in this case, it was found in a hole in the ground in South Wales).
 See also
- Fossil sorting by the global flood
- Living fossil
- Soft tissue preservation
- Transitional fossil