Well, hair doesn't rot really, just like bones. So they probably have found red hair aside Neanderthal bones.
About the blue eyes I don't know how they assume that. Probably genes in hair wich were still intact?
and btw this site explains a helluva lot for me :-)