Next time you leave your house, look in among the gravel of your path or drive. Drive gravel is usually quarried from glacial deposits - pebbles and stones that have been dumped in large numbers by melting glaciers. About 12,000 years have passed since the gravel was deposited, and the builders laid your drive. All sorts of things can be found in the gravel. Just because it was only 12,000 years ago doesn't mean the material is that young. One of the things you can find are fossilised corals from the Cretaceous (144 to 65 million years ago). These look like normal pebbles, but there is usually a honeycomb/sponge pattern on the exterior. You may also find teeth and small shells from the same period, or earlier. If you keep your eyes peeled, recent(ish) Palaeolithic fossils and artefacts occasionally turn up, but these are usually in poor condition due to the quarry crushers. While fossil hunting in a gravel quarry in Wiltshire, this Researcher found a Palaeolithic knapping tool and some deer bone scarred by someone's hand-axe approximately five to ten thousand years ago. The rest of it may be in your drive.
As a rule of thumb, the older the town is, the more geologically interesting it is. This is because it will almost certainly be built from locally quarried materials, rather than composites or stone from elsewhere (you can of course still find fossils in stone from other regions, but they won't give you much of an idea of what can be found locally). Although fossils will be found in most rocks, humans love to build with golden sandstone, or light grey limestone. This is primarily because it looks good, but also because there's lots of it nearish the surface, which makes it more economical to quarry. In the sandstones there tend to be a lot of brachiopods (think small, round mussels), and in the grey limestones you can find corals and crinoid stalks.
Crinoids still exist today and are generally referred to as 'sea lilies'. Crinoids, of course, look nothing like lilies. They look like plant stalks with great calcareous nets and fans emanating from the stalk. They are also animal, not vegetable, and the nets were used for catching tiny nutrients from the surrounding waters.
People have been known to deliberately place ammonites and other fossils into their walls. Keep an eye out for them, because for some reason they are often placed below or above eye level, sometimes making them difficult to spot. This Researcher knows of a man who sells slabs of building material laced with tiny ammonites - just right for a fire-place.
Cathedrals and churches are good places to spot fossils as they are usually made out of quarried stone, and often of more than one variety. You can spot the odd brachiopod in sandstone, but more interesting are the trace fossils. If the building has any Old Red Sandstone, it came from a delta system in a desert, similar to that of the Nile. If you can find a thin line of small pebbles running across the rock, this is evidence of a small flood, where the pebbles were washed and deposited by a wave of water. Other sandstones show a face of banding or braiding, where a current of water has run across the side of a river or stream, before the bank was turned into rock. Chunks of this material can record the flow of a stream for thousands of years, if you know how to read them. Also, look at the stones beneath your feet. In Wells Cathedral and others, slabs of dark rock brimming with bivalves (mussel-like organisms) have been used as pavement.
The best place to find fossils in your town, however, is the local museum. If you find yourself in Glasgow, take time to go and see Fossil Grove in Victoria Park. This is the floor of an ancient carboniferous (300,000,000-year-old) forest, replete with stumps and roots1. The Victorians saw fit to place a large, glass roofed museum over the site. Most museums have a collection of locally-found fossils, and if you record where they were found, you can go and have a look for some yourself. Steer clear of the quarries though, unless you have express permission and, ideally, a guide. They are dangerous places, and many use high explosives.