Fossils are rocks that contain the remains and DNA of Pokémon from millions of years ago. They are obtained from mining Fossil blocks, which are found between height levels 20-50 in gravel piles. They're fairly uncommon finds so it may take a while to find one. They will generate before any gravel in the world begins falling due to gravity so keep that in mind while searching. Fossil blocks are not affected by gravity.
When mined, the fossil block will always yield one of the nine possible covered fossils. These covered fossils can be cleaned in a Fossil Cleaner by right-clicking the fossil cleaner while holding a covered fossil.
Once you have cleaned your covered fossils, you will obtain one of the 9 types of fossils. These include the Helix Fossil (Omanyte), Dome Fossil (Kabuto), Old Amber (Aerodactyl), Root Fossil (Lileep), Claw Fossil (Anorith), Skull Fossil (Cranidos), Armor Fossil (Shieldon), Cover Fossil (Tirtouga), and Plume Fossil (Archen).
By placing one of the above fossils into a Fossil Machine, you will begin the process of resurrecting the ancient Pokémon within the fossil. The Pokémon you get depends on the fossil you put inside. Be sure to right click on the Fossil Machine and not the Fossil Cleaner. All Pokémon brought back to life through the Fossil Machine will start off at level 1.
The Armor and Plume fossils currently do not have a texture inside the fossil cleaner or fossil machine.
The Root Fossil currently does not work in the fossil machine. This is because Lileep (and its evolution Cradily) have not yet been implemented in the game.