How do we know Neanderthals DNA?
Neandertal DNA has been completely sequenced multiple times now, using DNA from bone and tooth samples found in cool or cold environments.  The first Neanderthal genome sequence was described in 2010:

A Draft Sequence of the Neandertal Genome

Since then, as well as higher-quality sequence, more genomes have been completed; at least 6 individuals have been sequenced (perhaps more; I've lost track a little).  As well, complete genome sequences from several Denisovans -- a Homo species that were approximately contemporary with Neandertals, but a distinct species -- have been recovered.

The science of recovering ancient DNA has advanced very rapidly in the last decade, and while it isn't routine to sequence 50,000-year-old DNA it isn't as magical as it used to be.  The current record for sequencing ancient DNA is 700,000 years, which is earlier than the sapiens/neandertalis split.