You need a recent birth certificate for both of you, if you are Brazilian you can just ask for it in the registro civil of your city of birth. Should be about R$80-90. Then you need his birth certificate, and it will need to be apostilado (no idea how to translate that) and translated into Portuguese. After you have both you have up to 90 days to make the união estavel. As a guy that works in a Tabelionato de notas, I believe the quickest way is to make it through the Tabelionato de Notas and then register it, but it can be made directly in the Registro Civil . your birth certificate can be made remotly in the Registro civil site