Start looking 4-6 month before you want to start.
Reason 1: There is a strong 3 month notice culture in Germany, so companies expect to have to start searching for a new employee 4-6 month before they actually need them (depending on how long it usually takes them to go through the applications, interview people and come to a decision).
Reason 2: To get the Arbeitsamt of your back. What dsoes your apprenticeship contract say about the end date of the apprenticeship? You need to notify the Arbeitsamt 3 month before your current contract expires (or before your expected graduation date, if you're a student or as soon as you know you're going to be out of a job, if that is less than 3 month before) in order to get unemployment benefits from day one if you don't find something immediately. They will schedule a meeting with you to discuss job opportunities and they will require you to start applying and write X applications / month. But if you can say you already wrote y applications and are going to interview here and there (or you already have a job lined up), they'll let you do your thing in peace for a while before they start bombarding you with "apply for this job or tell us why it's not a good fit" letters.