Go to Eterna City and gain the explorer kit from the man in the house next to the bike shop. You must then use the explorer kit to go into the Underground.
Once in the underground you must mine the walls; however, to get a skull fossil the last digit of the trainer ID must be odd. If it is even, the chances of mining a skull fossil are rare.
This article is a stub. Please help the Pokémon Wiki by expanding it.