Vertebrates have an adaptive immune system. It’s astounding from a biological and information theory perspective. Genes basically mutate themselves so they can form an enormous variety of proteins instead of the typical one to one mapping of gene to protein. Then there is a protein selection process that weeds out those antigens that bind to the host of that don’t bind to anything, leaving those that can bind to foreign proteins. (There’s another process to replicate antigens when they attack something.)
At least, that’s my primitive understanding. Come on HN, please someone fill in the real story, because I’d love to understand it better. :)