From Bulbapedia, the community-driven Pokémon encyclopedia.
Fossils are a trace or piece of an organism of the past, such as a skeleton, shell, or leaf, preserved in the earth.
In the Pokémon world, fossils of extinct Pokémon can be revived to life using techniques developed by the Devon Corporation, and a research laboratory on Cinnabar Island. The two processes were supposedly developed independently of eachother at around the same time.
Pokémon that can be revived from fossils currently include Anorith, Omanyte, Aerodactyl, Lileep, and Kabuto.
In Pokémon Red,Pokémon Blue, Pokémon Green, Pokémon Yellow, Pokémon FireRed, and Pokémon LeafGreen; Aerodactyl, Kabuto, and Omanyte can be revived using the Old Amber, Dome Fossil, and Helix Fossil - respectively.
In Pokémon Ruby, Pokémon Sapphire, and Pokémon Emerald, Anorith and Lileep can be revived using the Claw Fossil and the Root Fossil.
Pokémon who are revived using fossils are always part Rock-type. It is unknown if this is because that's the way they were in the past and their Rock-type allowed them to leave behind more complete remains, or if their Rock-type status is a side-affect of their origins.
In the games, very few Trainers possess Pokémon revived from fossils. Steven Stone, a rock-collector whose father is head of the Devon Corporation has two. Brock, a fossil enthusiast, has at least two himself in Generation II and in the Pokémon Stadium games. Finally, Lance posesses an Aerodactyl. Miror B. also has one on his team in Pokémon Colosseum.
In the anime, most fossil Pokémon are in fact, not extinct - but have simply been hibernating underground for millions of years. However, Dr. Moroboshi and Gary have both used research to directly revive fossil Pokémon.