Finding fossils can be an adventurous and exciting hobby. Each discovery is a window into an ancient world, full of mystery and learning.

[edit] Steps

Research your local geography. You cannot dig in solid rock, nor would you expect to find fossils in the local playground, but it could happen.
Look for areas with public access, but not under direct juridiction of local, state, and federal park services. These agencied do not usually permit you to dig and remove any specimens.
Talk to the local geological, archaeological, and historical societies. They are often happy to share their knowlege with you. Museums and libraries are also good sources for diligent researchers.
Gather some basic tools and materials, depending on the digging location and geology. This might include a mason's hammer, shovel, pick, brushes, a sifting pan or box with a hardware cloth bottom, and a notebook.
Dig material in a likely looking place in layers, removing scoops of rock-containing earth and sifting it in the "sifter, looking carefully at the stones you uncover. Fossils are simply impressions of animals, fish, or plants which have become part of the local rock, usually found in sedimentary rock. This rock is formed over a long period of time by deposits of silt and mud which have hardened to its present state.
Look closely at the stones, identifying the type you find. Silicates and basalts, which are shiny and fairly consistent in color and composition usually don't contain fossils, however, limestone consists mostly of calcium carbonate and can be a rich source. Fossils of sea shells and marine animals are common in the limestone used in highway construction, from grade aggegate, which is small pieces usually less than 2 inches across, to riprap boulders used to stablize drainage ditches.
Collect samples and interesting rocks to take home and clean up. We all would like to find a T-rex tooth or a Velociraptor, but the vast majority of fossils are less than one inch in size, and removing accumulated soil will reveal them.
Keep your eyes peeled. You are likely to make many interesting discoveries while you search. Petrified wood is common in many areas, and arrow heads and other Indian artifacts, unique crystals, agates, and semiprecious gemstones can be a reward for your efforts.
Think outside the box. Look in the gravel piles at landscaping supply stores and gravel parking lots where large, coarse stones are used.

[edit] Tips

We have found many fossils in the bottom of streams in deep pools of water where the currents accumulate stones washed in from the stream banks. These can include petrified wood, shark teeth, and various marine organisms.
Use a magnifying glass and different angles of illumination to look for unusual charactaristics in the rock specimens you gather.
If there is a reputable local outdoorsman you know, ask him if he has seen any unusual rock formations. A river near here in Florida and nearby in South Alabama has strata in the banks which are filled with small marine animals. An observant fisherman might see these and advise you where they are located, saving a lot of looking.

[edit] Warnings

It is unlawful to trespass on private property, so if you do not know who owns the land, find out and get permission before do any exploring.
Limit your exploration to your skill level. Do not go in dangerous terrain alone, and without proper equipment.
Watch for poisonous snakes and other hazards.
In the USA, when digging in developed areas, and especially in your own yard, always call 811 before you dig. One call to 811 gets your underground utility lines marked for free--helping save you from damage, injury, and fines. See http://www.call811.com for details.

[edit] Things You'll Need

A sifting box can be very helpful. You can build your own by cutting 4 1X4 boards about 18 inches long and nailing the corners together using 8d nails, then stapling quarter or half inch hardware cloth to the bottom.