Fossils are a planned feature for a future update. They were added as a pre-order bonus when the $750,000 mark was reached.
They are the remains of long dead creatures scattered throughout the Starbound universe. They are extremely valuable, very rare, and difficult to dig up. You will need special tools to clear the dirt and unearth a fossil. Removing the wrong piece of dirt could cause the fossil to crumble into dust. Successfully removed fossils can be placed as trophies. Some fossils so placed may even have special properties. Perhaps some of these long dead creatures can even be revived.