AFAIK, the change of Constitutions are "affirmative actions"1; since they are the basic law of the country there is no other law that can rule if they are "legal" or not. So, their only actual basis is "because I/we say so".
Now, there are a number of methods to give Constitution a degree of legitimacy:
Referenda asking for the people to approve or reject the new Constitution.
Approval by popularly elected representatives; either through the regular institutions (i.e. the representatives elected for the legislative body) or to specifically apointed Constitutional Conventions (representatives elected only to draft the new Constitution).
Imposition from the Head of State and/or single party (in dictatorships).
Those methods are not exclusive; you could have a Constitutional Convention draft a Constitution and then present it in a referendum to the public at large; or a dictatorship can decide to allow their legislative body2 to discuss the new Constitution as a way to give it credibility and also to cater to different sensibilities in the dictatorship power base.
1I am sure I am misusing the expression in a really horrible way, but you get the idea.
2After all, if it is a dictatorship the members of the legislative will be most likely in line with the Head of State.