Насколько я понял, если не считать всяких внутренних процедур, связанных с сертификацией перевозчика, знанием языка и т.д., необходимо наличие двустороннего межгосударственного соглашения о воздушном сообщении.
Вот интересно, а насколько детально в этом соглашении описывается частота полетов и маршрутная сеть? В частности, заявку на выполнение полетов даже не будут рассматривать, если "воздушная линия, указанная в заявлении, не соответствует таблице маршрутов, установленной межправительственным соглашением о воздушном сообщении (международным договором Российской Федерации);". Беглый поиск в гугле ничего по этим самым межправительственным соглашениям не дал.