Adding to comprehensible's answer, 99.9% similar DNA still leaves 0.1% of different DNA. Within this 0.1% would be enough differences to be able to find the differences that comprehensible mentioned. This is also how the ancestry tests that are so popular these days work.
Additionally, for that type of place-of-origin analysis, my impression is they commonly look at isotopes of chemicals found in the bones, and matching it to profiles found in other regions.
For example, let's say that an area we're interested in has high levels of isotope X but low levels of isotope Y in the water and food, which we discovered from examining the archeological record. If we find someone in that area whose bones have low levels of isotope X and high levels of isotope Y, we can conclude that this person traveled here later.