Юридически это всегда оформляется через помилование. Без указа президента ни один начальник колонии заключенного не отпустит - это будет чистая уголовщина, превышение полномочий или организация побега.

Каждая сторона подписывает указы о помиловании тех граждан, которых планирует отдать. Чаще всего эти указы секретные и не публикуются на официальных сайтах до последнего момента. Как только указ подписан, люди юридически перестают быть преступниками на территории этой страны, их освобождают из под стражи и они могут лететь куда угодно.

Знакомый из органов рассказывал, что сложнее всего договориться о паритете. Спецслужбы торгуются буквально за каждого человека как на рынке. До последнего момента никто не уверен, что все пройдет гладко. Один раз вылет задержали на шесть часов из за того, что у одного из участников обмена обострилась хроническая болезнь прямо в камере СИЗО и его не могли транспортировать. Все сидели на иголках, думали что сделка сорвется.

Все восхищаются гуманизмом таких сделок, но по сути это легализует захват заложников как инструмент международной торговли. Если государство знает, что за любого задержанного шпиона можно будет выторговать своих провалившихся агентов, оно продолжит хватать случайных иностранцев под надуманными предлогами.