Clearance:
Ask the yacht club (iateclube@iateclubedonatal.com) the day before you arrive to inform immigration (Policia Federal) that you would like to check in the next morning. The club can arrange for immigration to meet you the next morning in the Passenger Terminal (Terminal Marítimo de Passageiros, 1.5km from the yacht club). If that doesn’t work, you need to go by taxi or Uber to the “Superintêndencia Regional de Policia Federal” in Ria Doutor Lauro Pinto (20 min). If you don’t have a local sim card yet, you might want to take an Uber (using the yacht club wifi) to Midway Mall first to buy one at C&A, where they sell them without you needing a local tax number (CPF). The Mall is on the way to the Policia Federal.
Next, visit customs (Receita Federal), which has many different buildings. The office you need is in an annexe of the Passenger Terminal, accessible via the main entrance of the Passenger Terminal. Ask the guard to show you.
Finally, to the Capitanía dos Portos, just down the road in Rua Chile.
“Chegamos de veleiro” (“we arrived by sailboat”) was often enough information for the officials to understand what you needed.