"Who is in the government of the new prime minister?"
Translation:Wie zit er in de regering van de nieuwe premier?
Overheid is the general body as a whole and all parts it consists of, can be at any level: national, provincial, municipality. According to Van Dale: personen, lichamen aan wie het gezag is toevertrouwd, m.n. door de wet
Regering are the current rulers or the group of people currently ruling the state, so the prime-minister/president (depending on the country) with the group of ministers. Usually only at national level, Belgium also has regional ones (don't ask me for details, it's way to complicated for a non-Belgian).
Generally you use "overheid" for the "competent authority", this can be national, provincial or even municipal, and you use "regering" for the governing body (Executive power), and can also refer to the "coalitie in de Tweede Kamer" (coalition of the House of Representatives) . But most people use the two words interchangeable.