Unfortunately I don’t have any good references (especially not in English) and I know more about Swiss law than German law, anyways. However maybe some questions to keep in mind that need to be answered for such a project:
Disclaimer
Big disclaimer at the top: IANAL and this is not legal advice. At some point on this route you will need to get in touch with a specialist.
a) Legal form of the entity
The legal form influences what you can or cannot do with the entity. Basic options are:
i) A company (UG, GmbH, AG etc.)
Advantages: You own it and can do whatever you want with it. Maximum flexibility.
Disadvantages: Cannot be charitable (except “gemeinnützige GmbH”, see below), so you have to pay taxes and it might be more difficult to attract donors to donate to a company. For GmbH and especially AG you need to bring quite a bit of cash for incorporation. Legal / accounting costs are probably higher than with an “e.V.”.
ii) "Gemeinnützige GmbH"
A charitable company, pretty new possibility under German law, I don’t know anything about it but it might be worth researching a bit further.
iii) An association (“eingetragener Verein”, “e.V.”)
Advantages: Relatively easy to set-up (there are millions of them in Germany, so it can’t be that hard! ;)), can be charitable (if it satisfies the requirements, also see below), can have “members” which share the project’s goals.
Disadvantages: You do not “own” it, its members decide its fate. Depending on how broad the membership is, they can fire you and Gargron and you can’t do anything about it.
iv) A foundation (“Stiftung”)
In its most general form, a foundation is a bag of money with a purpose you have given it and some humans working for it that use that money to achieve that purpose. In practice, foundation law differs widely between countries and I don’t know much about Germany. I do think Germany’s foundation law is rather strict, so I’m not sure that what e.g. the Wikimedia Foundation is doing under U.S. law would work as a German foundation.
b) Members
If you are going down the association route, who should be able to become a member? You can restrict membership, so you could e.g. say that only the inner circle of core developers will be members of the assocation, or only instance admins or that anyone interested in Mastodon and sharing its goals can become a member.
The broader the membership gets, the more support for the project you may get (especially as membership usually comes with membership fees, which can be more sustainable than a month-to-month Patreon and more attractive as members get a say in the project in return). It will also make it easier to obtain charitable status (see below). However, the broader the membership also the more control you give away: the members, not you, decide on the fate of the association. So the closer to your inner circle you keep it, the more you remain in control.
c) Charitable status
An association can become “charitable” (“gemeinnützig”), which makes it exempt from many taxes (which not only saves money but also a lot of work!) and also allows donors in Germany to tax-deduct donations. I don’t know the particulars at what counts as charitable in Germany, though. I think Mastodon could work but is probably a bit in a grey area (compared to e.g. “ending world hunger” or so), so you would need to consult with a specialist.
In general, if your membership is more open it is easier to make a case that you are charitable than if only a select few can become members. It also depends a lot on how you word the goals of your association (e.g. “providing the world with a free and open medium for the exchange of ideas” will probably work better than “providing Mastodon users with the best user experience”).
d) Pay for you and Gargron
And maybe others in the future. 
How do you want to get paid? Options are:
i) Salaried employee
Probably the best option for you as employee, as it comes with social security and pension benefits and taxes are taken care of, as well. Will definitely need an accountant to do the administrative work for you, which will be quite expensive. At the current level of donations probably too expensive, but IMHO the right way to go long-term.
ii) Contractor
You write an invoice for your services, the association pays it. The easiest way from the association’s point of view, but you don’t get any social security benefits etc. If you are only working on Mastodon and are in Germany, you also need to be very careful as Germany has strict laws against “pseudo-contracting” (“Scheinselbständigkeit”) if you are basically working for just one organization the same way an employee would but claim to be a contractor (to avoid paying social security etc.). Needs careful checking to avoid you are not falling under these rules. Also, of course, you need to take care of paying taxes etc.
iii) Expenses for board members
If you are leading the association, you can claim expenses you incur and also a reasonable reimbursement for your efforts (“Aufwandsentschädigung”), e.g. for meetings you attended etc. This may be the simplest form, but it is obviously very limited in the amount of money you can claim as reasonable and it may easily lead into gray areas between employment and reimbursement. Needs careful vetting, I think.
e) Incorporation
If you have answered all the thorny questions above, incorporation is probably the easiest part: For an association, you need to come together somewhere, draw up a protocol of your founding meeting and agree on the by-laws / statues of the organisation (probably best to start from the by-laws from an existing association and adapt them to your need). Afterwards you need to register at the company register (“Handelsregister”). You need to check for Germany, maybe some or all of these documents need to be notarized or additional rules apply. Maybe there is also a minimum number of people you need as founding members of an association.
