役所の手続きですが、
事前に転出する役所で、転出届けを提出します。
この時点で新住所が決まってなくても大丈夫です。

通常、役所で転出届けを提出すると、
国民健康保険に加入していれば、その移転手続きも行います。

役所で、転出の証明書類が発行されるので、
引越しの際、忘れず持って行きましょう。

転出届けは引越しの５日〜１週間以内がベストかと思います。
転出届けを提出したら、印鑑証明なども自動で消去されます。

沖縄への引越しが完了し、新しい住所が決まったら、
前役所でもらった転出届けと印鑑を持って、
地元の役所へ行きます。
転入届けを記入して、提出すればOK。

この際に印鑑証明の登録もしておいた方がベストかと思います。
また、登録後、住民票や印鑑証明など２部ずつ程度、発行しておいた方が、
車の登録変更など、事務手続きなども出てくるので便利かと思います。

その場で、健康保険と印鑑証明カードは発行してもらえます。
手続きから発行まで３０分から１時間程度かかる場合もあるので、
時間に余裕を持って行きましょう。

国民年金や国民健康保険の支払い関係の書類は後日郵送されてきます。
基本、引越し月までは、前市町村扱いで翌日から新市町村になっている場合が多いです。

追記：
個人事業主や給与とは別で確定申告をしている方は、
引越し前に、税務署で納税場所の変更手続きも行っておきましょう。
税務署で、旧住所と新住所を書いて提出するだけです。

また、最近、沖縄に移住をしても、住民票を移さない人もいるようです。
これは沖縄を問わず、引越しや移住した際のもっとも基本的なルール違反のように思います。
その土地に住むことは、道路をはじめ公共サービスを利用します。
自分の住む土地に税金を収めることはとても大切なことだと思います。
最近、離島で幽霊移住者という言葉もあります。
住民票を移さず、人口カウントが出来ない人たちです。
またそういった人が、上下水の設備や地域のサービスに文句を言うなど、
モンスター化していて、地元では非常に困っているようです。
ただでさえ、地方は財政難な中、税金を払わず住人だけが増えるのは、
大きな負担になっているようです。
引越しをしたら、必ず住民票は移しましょう。