I'm a British citizen and have recently moved to Brazil on a tourist visa. I came specifically to be with my long term girlfriend.
I brought my passport (obviously), along with my birth certificate and qualifications.
Can you advise the process we need to undertake to be joined in holy matrimony and legalized here in Brazil?
Well, let's talk terminology, David. You have not "moved" to Brazil. You have at most been given a stay (prazo) of 90 days with (not sure currently about UK passport holders, but true for U.S.)possibility of renewal for 90 more by applying to the Policia Federal and paying a fee.
So the first thing to do is to go to the "cartorio" you intend to use for the marriage and inquire about which documents they need from you and which from the gf. Each cartorio is a private business and may have slightly different requirements. Unfortunately, you are asking this question after you have arrived in Brazil and some of the documentation may take time to be prepared (see below) for handing over to the cartorio. Most cartorios refuse to marry a couple when the gringo has overstayed his visa (although this is technically not legal to do, as you may find from reading some of the helpful threads on getting married in Brazil on the forum of the expat site gringoes.com). Much of this process could have been done in advance of arrival by drawing up a document at the Brazilian Consulate in the UK giving your gf power of attorney, but too late now. So realize that you may have gotten yourself into a situation where you have to go back to the UK and return after the 6 months required to stay out of Brazil after exhausting your total prazo.
Once you know from the cartorio which documents they require (and these are likely to be quite a bit more extensive than the birth cert.--don't know what "qualifications" refers to), all documents must be stamped and recognized (as being real and not forgeries) by the Brazilian Consulate with jurisdiction over where they were emitted. So a UK birth certificate would have to be brought to the Brazilian Consulate in the UK for this. Some trusted person in the UK would have to do all this for you and send the docs to you in Brazil. That person may need a power of attorney to act for you at the Brazilian Consualte in the UK.
When all documents are recognized (reconhecido), they have to be translated in Brazil by an official translator only (there is an official list of people qualified to do this).
While you are getting the docs for the marriage, add a current police report (to recognize and translate), which you will need to apply for "permanencia" (permanent residence) upon your eventual marriage if you intend to live in Brazil.
Then you bring all your recognized and translated documents, along with those of your gf, to the cartorio. They will schedule a marriage date (usually, where I live anyway, a ceremony with a group of couples) about 30 days out (time for the judge to review all the applications). They will help you register the marriage officially.
As you can see, it is a long, cumbersome and tedious process that you may not have time to complete before your prazo runs out.
Best of luck, though, for a happy future together.