You need to break rocks using TM06 Rock Smash. Certain places have certain chances of getting fossils, and some are version exclusive. In your case, Dome and Root Fossils can be found, and Helix and Claw cannot be found. Dome Fossils and Old Ambers are found in the Ruins of Alph, and Root Fossils are found in Cliff Cave.
See here for more information.