In order to establish permament legitimacy an English republican government would need the support of moderate royalists such as Edward Hyde and moderate parliamentarians such as Lord Fairfax. This would require a policy of religious toleration towards all Christian churches and sects (except Roman Catholics) which do not want to overthrow the Commonwealth.
There would also need to be a skilful propaganda campaign in which Charles Stuart (the eldest son of Charles I) is characterised as hardly more than a boy - irresponsible, a debauched whore-monger with a string of mistresses (and the contemporary equivalent of a playboy), in contrast to the sober, God-fearing, responsible, politically experienced, family man John Bradshaw and other members of the Council of State.
The execution of Charles I is presented as a "cruel necessity", something undertaken with the utmost reluctance because there was no alternative. Parliament had endeavoured for two years to come to a satisfactory agreement with Charles which would preserve his life and his throne, but he acted in bad faith by starting the Second Civil War in 1648. He could erven be compared favourably with his son. Perhaps John Milton writes some pamphlets for the government.
Royalists are royalists- they support the Stuarts and a return to monarchy. Under any Constitution they will be excluded from government- if you look at the various constitutional schemes offered post-execution all exclude both Catholics and Royalists from any participation in government. Anyone who wants a Republic is a regicide, and they can't risk royalists and a restoration.
Fairfax was appointed the head the judges who were to try Charles I. However, he thought the fix was in for Charles and refused to participate in the proceedings. He shortly thereafter resigned from the Army and stayed at his estate through the rest of the interregnum. He did not want to participate in a government of regicides, which
If after the failure of Charles Stuart's attempt to claim the throne and Royalist armies are defeated at Dunbar in 1650 and Worcester in 1651, and Charles returns to the Continent as in OTL, the Council of State must disband the army in order to avoid a military dictatorship. It would be advantageous to pay all troops who are not officers their arrears and possibly a pension based on their years of service in the army.
The Council of State dissolves the Long Parliament in Spring 1652 and elections are held to the House of Commons. A republican constitution for the Commonwealth is discussed and passed by the new House and approved by the Council of State.
Models which are available for a non-monarchical form of government include the Swiss Republic, Venice, the Judges of Israel, and the Roman Republic.
Has Cromwell died in this scenario?
The Long Parliament is no longer sitting following Pride's Purge, it has been turned into the Rump Parliament. Neither has the support of the Army though, the first opposing Army policy and the second an unhappy creature of the Army.
The Council of State was dominated by the Army, by the officers who are going to need the Army in order to disband Parliament and control the country until new elections can be held.
I think the best that could be done would be that instead of Pride's Purge and the Rump Parliament executing the King, the Long Parliament be forced to pass a Redistricting Bill, a Franchise Bill and an Elections Bill be disbanded, and new elections held in 1649. Catholics and Royalists can be excluded from voting or running for Parliament, and the Army enfranchised. Basically, force Parliament to pass some kind of Heads of/Agreement of the People Compromise. The new Parliament will have the legitimacy of the People, and be in a better constitutional position to execute the King.
By excluding Royalists and keeping the Army in the field, the Army Council would be able to basically control the election, accusing anyone too opposed to their agenda of Royalist sympathies. A constitution must be passed which will do what the Army wants it to do, and a Parliament must be elected the Army trusts not to try and prevent them from getting any owed pay or pensions. This kind of arrangement never existed (or was never allowed to exist) OTL.
After that, the Army can probably be pensioned off with land seized from royalists in England, and with most of Ireland.
If the republican government rules efficiently, copes as well as it can with the Great Plague in 1665 and the Fire of London in 1666, and avoids disastrous foreign wars, by the 1680s it will have achieved widespread acceptance at home and abroad.
As in OTL, an English or British republican government would have an anti-French foreign policy. There would be the same alliances in the Spanish War of Succession and the Seven Years War (the French and Indian War in North America), with the same problems arising in the American colonies after that war.
Actually, the Commonwealth allied with France, and New Model Army troops fought in France for the monarchy during the Spanish Fronde (Turenne versus Conde). The Commonwealth viewed Spain as their larger enemy- Cromwell wanted to conquer Spanish America.