Ну как — компас, циркуль-измеритель, секстант, хронометр. Первым ориентируемся по сторонам света (что и без него можно сделать, но так проще), вторым оцениваем расстояния на карте (зная масштаб), третьим определяем широту (за счёт высоты солнца, но вообще им можно измерить ещё много чего для навигации — расстояние до объекта известной высоты, скажем), последним — долготу (за счёт разницы времени астрономических событий на месте и там, где хронометр настроили).
До изобретения секстанта и морского хронометра применялась астролябия (гораздо менее удобна, но известна ещё с Античности). Дата по секстанту спорная, но в общем это уже Новое время, как и по-настоящему точные хронометры. Компас был известен с XII века, вполне средневековый инструмент.
Точки отсчёта бывали разными. Гринвич как нулевой меридиан предложили ещё в XVI веке, но окончательно все на это перешли в середине девятнахи. До того бывали другие варианты: скажем, Азорские острова или Канары (популярный вариант в XVII веке). По сути не имеет значения, какова точка отсчёта, главное считать правильно.
Всемирной стандартизации карт, конечно, не было. Процесс начался только в 1871 — с первым Международным географическим конгрессом. Прежде составляли их сильно по-разному, но для опытного в навигации человека это какой-то уж прямо трагической проблемы не составляло. Всегда можно разобраться, как конкретная карта устроена, если вообще умеешь с ними работать.
К слову говоря, все эти навыки у моряков до сих пор есть, несмотря на всякие технологии. На всякий случай.
Ну а "в чём измеряли расстояния" — кто в чём, это до сих пор в мире не стандартизировано окончательно, как известно, несмотря на существование Международной системы единиц.