There are four different past tense forms for the German verb müssen (must). The easiest one to deal with is the simple past:
He had to eat the chocolate.
[Literally: He “musted” the chocolate eat.]
Who wouldn’t want to do that! Notice that while there is no past tense form of the English verb “must”, German does not suffer from the same problem. “Musste” means what “musted” would mean in English… if it existed.
The simple past of müssen has to be conjugated according to the person and number, just like every other German verb:
wir mussten – ihr musstet – sie mussten
The infinitive after müssen always goes at the end of the sentence (which may sound strange to native speakers of other languages, but that’s just the way it is):
The (present) perfect
When we want to convey a sense of finality, i.e. of something that has ended, we use the present perfect. The past participle of müssen is gemusst:
I had to. / I have had to.
[Literally: I have “musted”.]
However, beware! You will almost never see the form “gemusst” in practice. The reason is that the form “gemusst” is never used in connection with another verb. Instead of machen gemusst, we keep müssen in the infinitive and say machen müssen.
Note that, unlike English, you can use the present perfect with events in the past in German (and, in fact, this is the most common way to express the past in contemporary spoken German). For instance, you can say “Ich bin gestern ins Kino gegangen”, literally “I have gone to the cinema yesterday”. This is not possible in English, so we have to translate such sentences using the simple past.
Gemacht haben müssen
The pattern jemand muss etwas gemacht haben (“someone must have done something”) is used in the same way as in English. We use it to express that we are sure about something, as in
The gardener must have done it. He is the murderer. Er muss die Schokolade gegessen haben.
He must have eaten the chocolate. Die Läuferin muss schneller geworden sein.
The (female) runner must have become faster.
Note that the past perfect of the verb werden (to become) is formed with the auxiliary verb sein, not haben, which is why the form after muss is geworden sein, not geworden haben.