How much political influence is involved in the academia in Germany? I heard that German national politics influences the appointment of tenured positions in their universities. 

E.g. if some party is in power, they would like to see somebody loyal to them as the head of a faculty or even the rector of the university. Also, if someone is loyal to the party in power, his PhD students have better chance of getting into the university and obtain tenure. 

I also heard that, even getting a "Habilitation" requires a lot of political backing. 

To what extent is it true?
The answer is a definite no, none at all. Each open professorship is filled by a committee consisting of students, employees and other professors at the hiring institution.¹ There is no political appointee in those committees, so there is no way for national politics to influence those. There is of course a lot of internal bickering between the professors involved (which is what most people mean if they talk about politics in an university), but nothing to do with any political parties.

Appointments of higher positions such as the rector are a bit more involved and the details may vary a bit more between different universities, but the principle is the same. Normally the decision there is made by the senate (of the university), which in turn was elected by students and employees.

In general, there is a reason for all of this, which is the German constitution, which, in order to prevent history from repeating, in article 5, paragraph 3 specifically states that "science and teaching is free", meaning free of political influence.² This includes all specific appointments. So while some politicians might try to wield some influence, any attempt to actively get a specific candidate appointed for political reasons will be met with strong backlash and a successful challenge in court.

There is one famous exception, which is theology, where an appointment can be blocked by the corresponding church. There was a scandal last year, when a bishop seemingly tried to force his preferred candidate this way, but again this has nothing to do with national politics.

¹Technically they just decide on a list of three people, which then is given to the university administration and in some places to the ministry, but if they cannot state a compelling reason to do otherwise, those then have to take the first person in the list. Except in those rare cases the second and third choice are basically spares, in case the first declines.

²Specifically, this is one of the few unchangeable articles that not even parliament is allowed to abolish. They aren't taking any chances this time.