What you are looking for is sedimentary rocks. These are the ones that look like they have layers. They do. The rocks were created layer after layer as dirt or animals fell to the bottom of a lake, marsh or sea. Granite and rocks that were formed from volcanoes generally do not contain fossils. It was just too hot.
There is a certain amount of colour coding. Red is bad, black or grey is good. There are not guarantees that any rock will have fossils, but some have a better chance. Since sedimentary rocks are formed under entirely different conditions, some can be 'fossiliferous' while others, formed at the same time, will have very little of anything but rock. Red sedimentary rocks were likely exposed to the air as the sediment was being laid down and oxidized. These are not good conditions for fossils and chances are that anything like plants or animals decomposed before they could be preserved. Black and grey are signs of an oxygen-free environment (such as underwater) which is better for preserving the material.
Don't take a fossil out of a rock face or cliff without checking with someone first, you could break it. Researchers also need to know exactly where the fossil was found in the rocks to glean information from its surroundings. Call a museum, government or local university paleontologist first.
If the rock has already fallen from the cliff or broken away, that's fine.
One of the most useful tools for fossil hunting - aside from a hammer and chisel - is a geological map of the region or geological guidebook. The map shows the different rock formations. Such maps are available from the Atlantic geoscience Society through the New Brunswick Museum. Similar maps are also available from the Department of Natural Resources and the Geological Survey of Canada.