Usually, a change of government in a state is recognized as a matter of course by the international community. But in cases of coups d'état, or other inconsistencies with the general principles of the state's constitution, recognition becomes questionable.
When discussing the recognition of government it is implied the state remains physically the same (even if it's given a new name) and only the government or head of state changes. The question of recognizing a new government is the question of acknowledging a new representative of a state to the international community, nothing more. But this is not a trifle matter since the only way for the state to do business with other states is if it has a recognized representative.  A recognition doesn't necessarily imply that diplomatic relations will be established or maintained, though, the only limitation the recognizing state brings upon itself is that it can hardly recognize any other government of the state unless the already recognized government falls from power.
There are two main issues demanding exploration: First, in which cases a change of a government can be called into question; and second, what the criteria for the recognition of a new government are.
Generally, a change of government isn't called into question as long as the head of state remains the same. The recent history of Greece is an example of this: In 1967 the government was overthrown by a military coup, but the formal head of state, the king, remained and there was no question of recognition. But when the military deposed the king in 1973 and thus changed the head of state, the question of recognition arose. During the Cold War, the recognition of governments were often relative to the policy of the new government. If the government's alignment in the Cold War was unchanged the powers often saw little need to question the change, regardless of how the change of government came to be. This may seem arbitrary, but that's how it is.
Regarding the criteria of recognition, it is debatable whether such criteria even exist. Some argue it is only a matter of politics. Nonetheless, the following arguments have all been used at one time or another:
- Public support, democracy
This is not unambiguous: After the presidential election in the Philippines in 1986 both Corazon Aquino and former president Marcos claimed to have won the vote; and during the Cold War public support (or the lack thereof) was the reason the Soviet Union recognized communist China and the reason why the United States did not. But lack of public support meant no recognition for the coup against Gorbachev in august 1991 or for the coup against Aristide in Haïti the same year.
To use this criterium some idea of what is legitimate in the first place is obviously needed. This is often found in the state's constitution. Thus in the case of a monarchy like Saudi Arabia it would be a question of the right heir to the throne, and in the days of the Cold War it could be finding the legitimate ruler of a communist system, whomever that might be. The international community might not recognize the legitimacy of the constitution in which case they usually compare the situation with what is constitutional in their own states, and nowadays, under the hegemony of liberal democracy, the criterium of public support often surpasses legitimacy as criterium.
- Ability and will to fulfill the international obligations of the state
For this criterium to be met, not only must a foreign minister be appointed, but the government must voluntarily accept the international obligations made by the former government. While this has been an argument against the revolutionary new governments of China and the Soviet Union it is now almost out of use.
- Independence of foreign military power
This criterium is not used in the case of foreign military powers helping create a change of government, but is invoked when the new government is based on the continued presence of foreign military: So-called "puppet regimes". This was widely used to deny recognition of governments during the Cold War, and might see a resurgence in the war against terrorism.
- Human rights
Even though the issues of human rights are often brought up in international politics as a tool to discredit and condemn states, it has only rarely been used as a criterium for recognition of governments. At present, it is in practicality supplanted by the criterium of public support.
The above arguments have been used historically, but there is no discernible pattern to when one argument is used over another, and there are no treaties on this matter. Only a few restrictions are definite. For instance, a premature recognition can be considered an unlawful intervention in the internal affairs of a state. This was the case when Germany and Italy recognized the nationalist government of Franco in 1936 when the Spanish Civil War was far from decided. Failing to recognize a change of government when the old has obviously fallen from power could also be considered an unlawful intervention. The insistence by which imperial China, France, Italy and the United States maintained diplomatic relations with the government of the Tsar long after the Russian revolution is an example of this. The western powers' recognition of the taiwanese government in lieu of the communist Beijing as the true government of China after World War II might also be an example.
The main criterium for recognition is, thus, whether the government has an effective control over the state territory. This is simply the definition of what a government is and was adopted early on. Sometimes states would recognize governments as the de facto government, if they had gained at least a temporary effective control of the state, and then recognize the government de jure when it had gained seemingly permanent effective control. The former Canadian foreign minister Mitchell Sharp once said: “While the act of recognition is essentially legal in nature, the relevancy of political factors is recognized in modern international practice; each situation is therefore considered on its own merit.”.
Still, the idea of effective control as the only criterium was weakened during the 20th Century. For one, the many exile governments during World War II was still seen as the true governments of their countries. It is clear that while politics may cause the international community to turn the blind eye to some questionable changes of government, several of the criteria mentioned above, especially public support, is becoming a de facto criterium for the recognition of a change in government.
The list of states currently recognized by the United States:
(This is part of my personal quest (study) on international and humanitarian law)