Fossils are most commonly found in sedimentary rocks formed by the accumulation (deposition) of distinct particles or sediments in layers. Sediments may be transformed into rock (lithified) either by compaction or by cementing the grains together.
Some of the major types of sedimentary rocks which may contain fossils:
SANDSTONE - formed by cementing of grains of sand (any particles between 1/16 mm and 2 mm in size); Commonly deposited in rivers, dunes, beaches, and deltas.
SHALE - term used for rocks made of clay that has been compacted together or cemented. Tends to be easily split, either into thin sheets (laminae) or in a less perfect split (fissile). The sediments can settle out in seas, lagoons, and river floodplains.
MUDSTONE - like shale, but a more general term typically used for rocks made of mud (clay and silt-sized particles, less than 1/16 mm) that do not split easily into layers. Formed in many of the same environments shale is formed in.
SILTSTONE - rock that is made up dominantly of silt-sized grains, more gritty than shale.
LIMESTONE - rock usually made up of skeletal material (fragmented shells, corals, etc.) that has been cemented together. Typically accumulate in shallow, subtropical or tropical seas, even though some limestones form in deeper waters by chemical processes or the accumulation of calcareous plankton.
DOLOSTONE - rock made of calcium magnesium carbonate (dolomite). Two major varieties. One, formed by dolomitization of pre-existing limestone, is typically poor for fossil collecting because the rock-changing process commonly destroyed the remains. The other type of dolostone apparently formed as dolomite precipitated out of abnormally saline seawater: this is the main rock that contains fossils of eurypterids.
Because fossils are usually found in sedimentary rocks, it is important to know at least some of the basics about stratigraphy, the study and interpretation of layered rock. Sediments are originally laid down in horizontal layers, so if you find rocks tilting at an angle something had to have happened to move them to a new orientation. Sediments are deposited so that the layers on the bottom are older than those on the top ("superposition"), so as you collect from an outcrop the fossils you find at the base represent organisms that lived before those represented by fossils you collect from higher up.
As you collect fossils, you will undoubtedly notice that a particular rock interval at one locality may look a lot like a rock at another. Sediments, especially those deposited in marine environments, are laid down over large geographic areas, and the individual exposures you go to are but local scratches into the total sediment body. Stratigraphers use various techniques of correlation (establishing equivalence) to show that a particular rock in one exposure is part of the same body as rock seen elsewhere.
Rock sequences are divided into a hierarchy of rock units, each distinct from those above and below. The basic rock unit is the formation. Formations are grouped together into larger units called groups, and can in turn be subdivided into members based on more subtle differences. Some members can be divided into even smaller submembers. Also, individual beds, may be distinctive enough that they can be recognized across great distances.
Rock units are given two-part names so they may be consistently referred to. The name's first part is the "type locality," a place where the unit is relatively accessible and exhibits its major characteristics. The second part of the name is either the dominant rock type or, if no one rock type is pervasively dominant, the more general term ("Formation" or "Member," for example).
James Hall back in the 1800's was the first to apply the current naming system when he named the Rochester Shale for exposures of dominantly gray shale in the Rochester area. An example of a rock unit without one dominant rock type is the Grimsby Formation, which includes both sandstones and shales. Members, submembers, and even beds are now named the same way, with designation of a type locality. This may be confusing to the new collector, especially since beds characterized by particular fossils may have been originally named after the dominant fossil present. If you are going to really get into collecting fossils, it is a very good idea to become familiar with the names and characteristics of the rocks in the areas that you will be visiting.