In exceptional conditions, the feathers themselves can be fossilized! China's Liaoning province is one place where this happened - it had very fine-grained sediments capable of preserving exquisite detail in fossils. For example, we know that this small theropod dinosaur (Sinosauropteryx) had a layer of fuzz similar to down feathers. And Microraptor, a smaller cousin of Velociraptor, had full-on wing feathers, plus long leg feathers and a small feathery fan on its tail.

When feathers aren't preserved in a fossil, other evidence may tip off paleontologists to the likely presence of feathers. Quill knobs, bumps on arm bones where feathers attach, have been found in several dinosaurs (including Velociraptor itself). In addition, if a certain dinosaur has no direct evidence one way or the other, but has close relatives with confirmed feathers, it can be reasonably assumed it had them too. This is akin to how extinct cats are depicted with fur because all their modern cousins have it.

I'm assuming they used previously unstudied fossil markers plus new examination of DNA as it relates to currently alive animals.

Advances in technology change everything.

Cars, dinosaurs, energy production, what's really alive in dirt. Everything!