Они используют вероятностные модели на основе встретившихся в вашей ДНК генетических маркеров. Широко распространенным маркером является, например, гаплотип Y-хромосомы у мужчин (можно прочитать в Вики - en.wikipedia.org).
Вкратце, Y-хромосома первого мужчины Homo Sapiens с тех пор успела сложным образом мутировать, причем по-разному у разных его потомков. Потомки потомков наследовали, очевидно, эти мутации, по прямой мужской линии (потому как Y-хромосома) и добавляли к ним свои. В результате человечество сейчас разделено на десятки гаплотипов и еще больше подтипов, которые в разных регионах встречаются с разной частотой.
Аналогичных маркеров в человеческом геноме очень много и разных, и на основе того какие они у вас, можно анализировать популяционные составляющие вашего происхождение (из каких этнических или, если шире, расовых групп вероятнее всего были ваши предки). Надо отметить, что "национальности" для биологии не существует, существуют популяции. Соответственно, невозможно точно определить по геному, что вот этот человек - немец, а вот этот - француз. Немец из какого-нибудь Рура может оказаться генетически ближе к французу из приграничных регионов (да хоть и из Парижа), чем к другому немцу из Дрездена. Поэтому генетические тесты обычно дают разбивку происхождения не детальнее макрорегионов, иначе там достоверность очень низкая будет.