По разному. Поначалу португальцы ставили падраны - каменные столбы, символизирующие, что они первыми достигли эти земли (как минимум с 1488 г. - похода Бартоломео Диаша). Но это чисто для красоты.
Также (формально и "для красоты") заверяли нотариально. Вот запись из вахтенного журнала Колумба о первой высадке на остров Карибского архипелага ("факт открытия Америки" в 1492 году)
Пятница, 12 октября. В пятницу достигли одного островка из [группы] Лукайских, который на языке индейцев назывался Гуанахани. Тут же увидели нагих людей, и адмирал и Мартин Алонсо Пинсон и Висенте Яньес [Пинсон], его брат, капитан «Ниньи», с оружием съехали на берег на лодке. Адмирал захватил с собой королевский стяг, капитаны — два знамени с зелеными крестами. (А знамена эти адмирал держал как вымпел на всех кораблях, и на них были буквы «F» и «Y» (Буквы «F» и «I» — инициалы короля (Fernando) и королевы (Isabela). В XV веке имя Isabela часто писалось через «Y».— Прим. перев.), и под каждой буквой помещены были короны, одна слева, другая справа от креста.)
Высадившись на землю, они увидели очень зеленые деревья и много воды и различные плоды. Адмирал призвал обоих капитанов и всех прочих, кто сошел на землю, в том числе Родриго д`Эсковедо, эскривано всей флотилии, и Родриго Санчеса де Сеговия и сказал им, чтобы они под присягой засвидетельствовали, что он [адмирал] первый вступил, как оно воистину и было, во владение этим островом от имени короля и королевы, его государей, свершив при этом все формальности, какие требовались; более подробно это отмечено в актах, которые здесь же были составлены в письменном виде. Вскоре на берег пришло множество жителей острова.
(эскривано - как бы нотариус, юридический чиновник-секретарь для записи государственных актов - для того такого взяли в экспедицию).
Потом договорились юридически под патронажем Папы Римского (он, будучи "большим авторитетом" в Европе "крышевал" этот "понятийный" договор) - см. Тордесильясский договор от 1494 года (позже корректировался) - все земли на восток от "папского меридиана" (по Азорским островам) - португальские, все на запад - испанские. Печать, подпись - Папа Римский. Аллилуйя. Так и разделилась колонизация новых земель - Индия и ЮВА отошла Португалии, Америки - Испании. Пока не подросла Голландия с её колониальными устремлениями, а чуть позже Великобритания.
Мнение Франции и Англии тогда спрашивать не стали, они решали свои междоусобные проблемы на континенте, Голландии, Германии, Италии тогда не было, была Священная Римская Империя, у России и западнославянских стран (Польши, Моравии, Чехии и др.) тоже были свои заботы на континенте.
Ну, а вообще, по практике, для удержания колониальных земель ставили форты, оставляли гарнизон. И для дальнейшего удержания колоний от притязаний других претендентов, включая местные туземные племена или колонизаторов мусульманского мира, надо было иметь хорошую колониальную армию и очень сильный флот.
В новое время (XVIII-XIX века) делали заявления об открытии новых земель в географических обществах (Франции, Великобритании - тогда они были в авторитете). Но форт, гарнизон, армия и флот тоже были нужны, чтобы подтвердить конкурентам "своё право" на эти земли.
Международный принцип нерушимости установленных границ (а также и принцип территориальной целостности государств) утвердился только после Второй Мировой войны (годам к 1970-м). А до этого - у кого флот и армия сильнее, того и земли (если готовы были и в Европе отстаивать своё уверенное доминирование над). А так и в 1982 имела место война за Фолклендские острова между Великобританией и Аргентиной (не говоря про современные реалии). И это показательный пример по вашему вопросу - см. ссылку.