The first fossils you are able to get are in Route 111 (In the desert, which requires the Go-Goggles). You need to climb up the tower by using the Mach Bike since there are cracks in the floor that will make you fall unless you use the bike. You also need to take a Pokemon with Rock Smash to advance foward. You have the option of getting the Root Fossil (Lileep) or the Claw Fossil (Anorith), however you can only get one. You can get the other fossil after you beat the game in the Fossil Maniac's home. They are items that you are able to interact with in the top. The tower itself shows up randomly, so if it doesn't show up, just exit the desert and keep entering until the tower shows up.
Hope this helped! =3
