Before registering with the university, you need a certificate of health insurance. To get coverage, you can, for example, join the AOK / Allgemeine Ortskrankenkasse (they've got a booth under the stairs in the Mensa building (D4.1 on the map)) or the TK / Techniker Krankenkasse. Both are so-called "Gesetzliche Krankenkassen".
Regardless of which health insure you choose, you will need to bring along your "Zulassungsbescheid" from the university. They will also ask for your bank account data, so that they can debit the amount of the contributions directly.