How is it known that Homo sapiens and Homo neanderthalensis interbred?
Although this question makes some false assumptions, it is fundamentally interesting as the methodology used is neither simple or easy to understand. It is not my area, but I have found it especially interesting to read the long 2010 Science paper by Green et al.. One really needs to read it for oneself (it is free view), but it is not a trivial undertaking.

False assumptions / misconceptions in the question

The main misconception in the question are:


That it is necessary to know anything about the genome of H. erectus to make these conclusions. The methods used do not require this. (Although comparison with chimpanzee is sometimes used to give an indication of whether a genetic change occured in humans or Neanderthals.)
That the similarities and differences under discussion relate to differences in complete genes — “but gene B was not already present in H. sapiens…”. They do not, which makes the analysis more complex to follow.


Towards an explanation

Let me start by addressing the question “What distinguishes those genes (purported to have been acquired by H. sapiens from Neanderthals) from genes that both species inherited from a common ancestor?”. The answer relates to the absence of such genes from modern humans of African origin, and the fact that we know the general evolutionary relationship between neanderthals and modern humans (African and non-African) from a wealth of non-sequence paleontological evidence. This is shown in the diagram below, modified from a recent and recommended review by Nielsen et al. in Nature (2017). 



Clearly any gene present in the common ancestor to humans and Neanderthals should be present in both African and European populations, unless it had been lost from the African population.

So if the analysis is not done by detecting gain/loss of individual genes, how is it done? Certainly not by overall percentage sequence similarity, because of the high overall similarity and the population variation. It is done by studying SNPs — single nucleotide polymorphisms — in particular genes. 

For example, consider a gene that has only a single haplotype in Neanderthals, and originally had a single but different haplotype in humans. (This might determine something like eye colour, although this is not an actual example.)  If the other haplotype were acquired by humans as a result of interbreeding, then the modern human population would contain both alleles. When you compared the relationship of the SNPs for this gene between different humans and between humans and Neanderthals you would find different results from those for a gene the variant of which had not been acquired by interbreeding. The acquired gene in humans would be more related to that in Neanderthals than non-acquired genes, but less related to that  in other humans (because of its more recent appearance in the population and time for homogenization, I believe).

The African/non-African aspect is explained in the Science paper cited in my introduction, but there is a good visual diagram in a 2014 Nature paper by Sankararaman et al., the manuscript of which can be viewed freely in PMC through the US HHS.



(1) Sites where a panel of sub-Saharan Africans carries the ancestral allele and where the sequenced Neanderthal and the test haplotype (marked non-African) carry the derived allele are likely to be derived from Neanderthal gene flow; (2) Haplotype divergence patterns. Genomic segments where the divergence of the test haplotype to the sequenced Neanderthal is low while the divergence to a panel of sub-Saharan Africans is high are likely to be introgressed.

These papers contain a wide range of controls, including comparisons of different non-African population groups, and detailed discussion of alternative possibilities.

A final point of interest is that Sankararaman et al. examined some of the genes in which these SNPS suggest Neanderthal origin. They write:


  “…genes involved in keratin filament formation and some other
  biological pathways are significantly enriched in Neanderthal
  ancestry in European populations, east-Asian populations, or both
  …. Thus,
  Neanderthal alleles that affect skin and hair may have helped modern
  humans to adapt to non-African environments.”


Coda

It would be scientifically dishonest not to mention some oddities. One is that the Green et al. paper suggested that gene flow had been uni-directional: from Neanderthals to humans, which is apparently unusual in interbreeding. However a more recent study (Kuhlwilm et al., 2016) shows some human gene flow into Eastern Neanderthals, although not into European Neanderthals. (Thanks to @iayork for pointing this out.). The other is that modern Asians appear to have more Neanderthal DNA than modern Europeans. (This is discussed in the paper already mentioned by Green et al.)