The Chancellor of Germany is elected by the parliament (Bundestag) with absolute majority. This is done during the first session after each election. Additionally, the Bundestag can at any time do a motion of no-confidence and vote a different chancellor. The Bundesrat does not have any say in this.
Officially, the cabinet members are then chosen by the newly elected chancellor as he or she says fit. But unofficially, the cabinet members are usually negotiated during the coalition agreement.
So what's the coalition agreement?
There wasn't a federal election since 1957 where a single party obtained 50% of the seats. So if every party would vote for their own chancellor candidate, there would never be a government. But why would any party vote for the chancellor proposed by the political opponent? Because they get something in return.
Two parties which together hold at least 50% of the seats in the Bundestag will form a Coalition (theoretically it can of course be more than two. But even though it was discussed from time to time, so far this hasn't happened on the federal level). This coalition is usually manifested in a coalition agreement which includes:
- Which party chooses the Chancellor
- Which party chooses which cabinet member
- What policies will be done in the next four years
After they came to an agreement, the parliament members of the coalition party will all vote for the chancellor they agreed on, who will then nominate the ministers they agreed on. The members of the coalition parties will also be (unofficially but strongly) obligated to support any of the policies which were agreed on in the coalition agreement.