In Black or White 2, you will only be able to find Fossils after you've beaten the Pokemon League and have access to Nascrene City and Twist Mountain.
In Nascrene City, you can go inside what used to be Lenora's Gym. She will be there to greet you and gives a choice between the Plume Fossil and Cover Fossil.
In Twist Mountain, there is a worker in the lower levels who will give you one of each of the other fossils each day you go and talk to him