По звездам.
Забавно, что в вопросе упоминается GPS - ведь приемники теряют сигнал даже в деревянном деревенском доме. Что уж говорить о метрострое, где тоннели могут располагаться на глубине нескольких десятков метров.
Зато совершенно безукоризненно продолжает работать компас. Хотя для прокладки маршрутов обычно пользуются даже не магнитным, а гирокомпасом. В сочетании с различными средствами измерения пройденного пути это дает потрясающие результаты.
Ну, и еще одно совершенно замечательное средство для ориентирования на местности - это различные технологические, вентиляционные и т.д. шахты. Всегда можно выглянуть на поверхность и понять, что шел на Одессу, а вышел к Херсону.
Точно также, как и раньше, ничего не изменилось. GPS под землей не помощник. У человечества есть многовековые знания того, как "копать под землей", потому что веками под землей строились шахты и подземные ходы, порой на десятки километров. Существует даже такая профессия - "маркшейдер".
По фотографиям выходит, что первые метростроевцы строили туннели вообще как бы "под открытым небом". То есть ориентироватся было достаточно просто. Но это про первые тоннели, которые ещё не глубоко закладывались. Вырывались места для прокладки тоннелей и дальше уже всё остальное.