1) everyone has a government-provided ID document: a passport, for German nationals the ID card Personalausweis also works, and for EU nationals (who can vote in municipal and EU elections) their country's ID document
2) the legal requirement to register at the city/region office ("Meldebehörde") where you live, and you have to prove this with a copy of your rent contract or property deed
3) everyone getting a document ("Wahlschein") by mail a couple of weeks prior to election date. If you don't get one but should have gotten, you can contact the election authority to investigate, and if you lose/misplace it you can easily look up where your voting place is, go there and have them locate you on the voter roll.
4) if any piece of official mail goes returned by the post as "undeliverable", the Meldebehörde will investigate and de-register you (thus also removing you from the voter roll)
The only real vote fraud in the last years was from a politician who had seasonal workers register at a company and apply for mail-voting, but that's it.