This should be easy, given how close we sometimes seem to already existing in some kind of cyberpunk dystopian vision of the near future, but I'm having a bit of trouble imagining exactly what the transition(s) to and structure(s) of corporate nation-states, as opposed to our present standard-fare representative governance nation-state, would most plausibly look like, given a starting point of roughly the early 2000s as the earliest possible point of divergence from the history you and I are familiar with as "true."
To be clear, I am talking about a very common trope of Cyberpunk - that nations, such as they are, will be balkanized, neutered little things, largely co-opted by the corporate interests with holdings inside their borders, in the future. That in many places there might actually exist districts, cities - even states with ONLY corporate and/or criminal syndicate power structures in place. It's a wonderful thematic tool for pasting the oppression, corruption, waste, and inhuman bureaucracy of authoritarian governments onto the template of corporations in order to criticize extreme visions of unrestricted capitalism, but is it plausible, and what would it look like?
Subquestions within this overall question that would add to any answer:
What would the relationship between corporation and nation look like?
What would be the most common relationship between employees and corporations look like?
How would corporations change?
How would concepts of citizenship, suffrage, and legal representation for individuals and organizations change?
Would there be any semi-stable transitional stages from government rule to full-blown corporate hegemony?
The East India company basically ruled India. They directly competed with other East India companies, sometimes directly, and enjoyed a monopoly on trade in the region sanctioned by the English crown. Thus while they were propped up legally by the English, the company itself often held sway in India proper. The nature of the power structure seems fundamentally to have been one in which the company posed as an intermediary between the west and the various regional principalities of India, controlling their governments by monopolizing the income available to them and pitting them against each other to keep them in check. They loaned the British government significant sums of money, essentially propping up Britain in dire straits and profiting immensely from its monopoly so bought in times of relative prosperity, where its products were readily consumed by the British public.
The BEIC marshalled and directed its own navy and army in campaigns and garrisons, with personnel drawn primarily from the native population whose lands it owned. These forces were used to enforce Company directives among the native governments. This force made the BEIC kingmakers. Such arrangements with local governments ensured the company did not incur the costs of governance - inimical to profits, especially when tasked with ensuring the compliance of native populations. This was fundamentally possible due to the power vacuum ensuing the fall of Mughal greatness by the rise of the Marathas and other Hindu groups in India - regional hegemony was in the hands of no one in particular.
Company profit was extracted at the expense of sustainability, to put it lightly. Regional stability and rule of law suffered consequently; India was in that time a nation ruled by a company and the thugs who did not get in its way.
Its corporate lobby was responsible for things like the Tea Act, which precipitated the emergence of the USA - and the undermining of Chinese rule of law via international opium drug trade.
Fundamentally, the BEIC was a joint-stock company insured by the British government and capable of almost unhindered operation throughout the subcontinent and much of the high seas. It was dissolved ultimately by an act of the British government in the wake of rebellion on the subcontinent which saw the company's military control of government there dissolve.
The BEIC was basically everything anyone could want of a horrifically omnipotent, octopoid, corporate stand-in for government.
These large Japanese business interests get disproportionate mention in Cyberpunk, probably fueled by western fearsin the 1980s, the decate in which we may say the genre was born. Fundamentally the amalgamation of a private holding company, industrial conglomerates, and a wholly-owned and backing banking organization, Zaibatsu basically ran Japanese economics, including tax collection, especially prior to WWII. Their differentiation from criminal Yakuza is sometimes hazy, and they also ran political organizations and engaged in quite a bit of military-industrial complex-ing. Their employees expressed considerable devotion to zaibatsu interests likely stemming from a cultural background encouraging such behavior. Their dominance came to an end with the fascist government of the 1930s and 40s nationalizing many of their assets.
Zaibatsu represent a blurring of the lines between family, corporation, government, and the individual, enabling remarkably stable and potent power structures to exist within a more powerful government.
Banana Republics When you have a country whose economy is based on the profits of a few or even just one company, you have a banana republic. While in a large and complex way one might consider the BEIC's rule over India a kind of very large and powerful Banana Republic, the Latin American examples of history provide a more recent and plentiful set of stories to draw inspiration from.
Banana Republics expose salient features of corporations which assume features of the nation-state: effective monopoly on trade and the backing of a foreign power more potent than the government in whose lands they are doing business.
In a very literal sense, organized criminal activities constitute nothing less than the unsanctioned operation of a "government and corporation" within the borders of one or more nation-states. Whereas these organizations are forced by the extralegal nature of their operations to utilize security enforcement and legal codes of their own design in place of the systems they subvert, such groups are immediately to be considered candidates for cooperation with corporations wishing to extend their influence within jurisdictions these groups exert influence upon. These mafias often arise most powerfully in the presence of disadvantaged identity groups which help to guarantee the loyalty and trust which transcends loyalty to and trust in the governing organizations they supersede. In situations where these organizations face no real pushback from existing governments, they themselves become the government.
Considering the above, it seems most likely to me that transition from modern customary representative nation-states involves the arrival of various converging states of affairs in a single jurisdiction:
Superior foreign backing
Local power vacuums
Corporate monopoly of trade
Displacement of trust and loyalty in the population from their governments to their employers and/or local crime syndicates.
Interestingly, some of these seem to precipitate the others. If you have a corporate monopoly on trade and/or a large crime syndicate, local governmental power will ebb, leading to a power vacuum which makes it more likely a corporation backed by any number of more powerful foreign states could impose corporate rule over an area and win the short-tern trust and loyalty of a local population.
I foresee a transitional period during which increasing income disparity and the instability of a maturing global market dominated by disruptive technological innovators leads to widespread disparity in the well-being of nation-states around the world. Such variation makes it possible for corporations to pick and choose nations willing to back them which may also be more powerful than nations in which these corporations which to do business, enabling them to easily play upon local power vacuums to get their way. Initial deficits in enforcement would be handled either by mercenary/criminal partnerships or by proxy government forces as already modeled in our historical record.
There are not many clues about what kinds of corporations would be most apt for this kind of existence, but we may assume that both private and publicly-owned firms are liable. Ideally they will be international and liquid, capable of making large investments in new markets at the drop of a hat to take advantage of local imbalances. Conglomerates will be better positioned to take advantage of opportunities to establish monopolies on trade in a variety of areas. Unique company cultures with strong team-building aspects will probably also be prevalent among the early adopters of this company-as-nation move.
One thing that is really only inferred from the above investigation, yet which I believe will also be fundamental, is a breakdown in international law. This is a somewhat surprising conclusion, since it had often been assumed that Globalization would make transnational conglomerates with immeasurable wealth and influence more common and therefore more likely to take advantage of smaller nations, but I believe that larger governments are too able to intervene in such affairs so long as the international community generally agrees on the legal aspects of such behavior. For a company based out of China to exert undue influence in a small African nation, for example, the world community of nations must not hear the voice of that small African nation or be interested in coming to its aid. How such a breakdown in international law would occur is a speculation more suited to an entirely separate question and will not be further investigated here.
The Stable Final State
The transition reaches stable equilibrium when no governments or government coalitions stand which are capable of or interested in toppling corporate nation-states, and such nation-states are ingrained into the fabric of the societies they do business in. There can be no Economic Singularity, since this destroys the concept of a corporation, so it seems that for such a future to exist we might/must assume widespread proliferation of monopolies resulted in siloed, proprietary knowledge economies without significant to-market contributions.
What would the relationship between corporation and nation look like? It would be, in most cases around the world, one where a single corporate entity used the government as a proxy, or - as it might see it - a unique subsidiary public relations and regulatory asset. In other regions, government might have broken down completely; in these cases we would probably see corporations either pull out, leaving "criminal" enterprise to fill the power vacuum, or else very large corporations like the BEIC would operate as the government themselves at great expense - presumably for some correspondingly large profit.
What would the most common relationship between employees and corporations look like? While some corporations seeking intense loyalty might end up employee-owned in a bid to devise some kind of representative citizenship with suffrage within company structures, the zaibatsu model seems the likely stable structure which would obtain, notably only after it had been incentivized for some time by the existence of and hiring practices used in large, stable monopolies which would encourage such shifts in loyalty. A more in-depth analysis of this question in light of the rising contractor economy is probably worthwhile, but suffice it to say a traditional cyberpunk future dominated by massive all-owning corporations that for all intents and purposes own their employees as well is probably somewhat off the mark. More likely employees are bought and sold as a commodity off the government to which they ascribe - perhaps yet another staffing firm or one of the largely relict nation-states.
How would corporations change? Largely answered in the preceding questions, but of significant importance (and not yet broached) is the corporation's relationship with regulations. Without governments and non-profit regulatory agencies backed by governments to devise and promote market regulations, regulatory work must be done by corporations - especially considering most large markets would be made up of people basically working either for you or another competing conglomerate. Interfacing your Business Operating System with those of your trading partners would be a key concern, and would expand to include care for and build-out of infrastructure, as seen in some cases with the aforementioned banana republics. Many conflicts in such a future would surprisingly stem from disagreements over things like what file format to conduct purchase orders in, how to handle currency exchanges, what constitutes legal incorporation in a given jurisdiction, etc.
How would concepts of citizenship, suffrage, and legal representation for individuals and organizations change? In such a future, citizenship is equivalent to employment by a company or perhaps consumption of its products at a distant remove. Suffrage is to be equated with stock holdings, and legal representation, while perhaps conducted in the form of a government court, is in fact dependent on the business relationships which obtain between the stakeholders in a case and may in fact devolve into outright violent confrontation where these stakeholders do not understand the power dynamic between them.
Would there be any semi-stable transitional stages from government rule to full-blown corporate hegemony? I think that in fact such a future would represent a sort of semi-stable transitional stage in itself. It seems inevitable that such a future would sooner or later collapse into the functional equivalent of state capitalism as local monopolies completely supplanted all over forms of control in a region - the only twist being that instead of the usual modern case in which a government operates a company, instead a company would operate a government or governments.
Fundamentally, the typical cyberpunk future we envision is predicated on and exists entirely within some modern equivalent of the Dark Ages - a massive power vacuum left in the wake of a prior system's collapse.