The genetics
Cloning from ancient DNA is the device of the plot. The Professor proposes to recover DNA from a fossil and grow a new Seymour, and adds that the clone would also have the dog's personality and memories, which is the science-fiction part: a clone shares its donor's genes, not its experiences. The computer's ability to read Seymour's age at death from the sample is another comic liberty. The episode uses the idea not to explore science but to raise an emotional question, whether bringing back a lost companion would be for the dog's sake or Fry's. The Professor is the series' usual eccentric scientist, here a helpful one. Pets have been cloned in real life, but mammalian cloning requires intact, viable cell nuclei rather than DNA alone, so a fossil could not serve; the episode itself presents Seymour's rapid fossilisation as a special case.
The story
At a museum exhibit, Fry is shocked to find a fossilised dog that he recognises as Seymour, the pet he had in the 20th century before he was frozen. After he protests outside the museum for three days, he is given the fossil. Professor Farnsworth explains that, because the dog fossilised unusually fast, a DNA sample can be used to produce a clone, and even to restore Seymour's personality and memories. Bender, jealous of the attention Fry gives the dog, throws the fossil into a pit of lava, then regrets it and dives in to recover it. As the cloning begins, the computer reports that Seymour died at the age of 15, twelve years after Fry was frozen. Believing the dog moved on and forgot him, Fry stops the process. A closing flashback shows that Seymour in fact spent the rest of his life waiting faithfully outside Panucci's Pizza for Fry to return.