Assuming one is a permanent resident of an EU state other than Germany (e.g. Czech Republic), what documents are needed for them to work in Germany? The German Federal Office for Migration mentions that:
Residence permit for third-country nationals who have acquired the "permanent EC resident" title in another EU Member State
This residence permit will be granted to a third-country national who wishes to live in Germany for longer than three months
However it isn't clear if an EU resident can start working in Germany without any additional documents and then apply for a residency if deciding to stay for more than three months.
An equivalent Czech law mentions that it's possible to work without a visa if the person in question has been a permanent resident of the EU for more than 1 year. Unfortunately I don't know enough German to dig up the equivalent German law.