Remember that Sauron ruled most of Middle-earth beyond the borders of the Middle-earth maps, in Harad to the south and Rhûn to the east, and beyond those lands, for one or two thousand years during the Second Age, the Black Years of Middle-Earth.
Sauron was the direct ruler or the overlord of local monarchs, and he was worshipped as a god.
Only Númenórean settlements on the coast, and a few Elf or Dwarf realms, mostly in the northwest of Middle-Earth, escaped from Sauron's rule or control.
And after Sauron was defeated at the end of the Second Age, all those lands became independent, except for those which the Númenóreans took over. But If most of the people of Middle-earth were Sauron worshippers, they would not just automatically stop worshipping Sauron.
Many people in those lands would try to overthrow the Sauron religions, but the priests of those religions would resist those attempts. So in some countries the Sauron religion might be overthrown and prohibited, but secret cults of Sauron worshippers might remain, despite persecution, hoping for his return. And in other countries the Suaron religion would defeat those rebels and crush them, and persecute all who claimed that Sauron was a false god. The Sauron priests would claim that Sauron merely left as a test of how faithful his followers were, and was certain to return.
And maybe there were bloody religious wars between countries which still worshipped Sauron and those which no longer did.
Sauron was reduced to a mere spirit after being killed on Mount Doom, and nobody knows exactly how long it took him to make a new body for himself. It might have taken him a thousand years, for example, to take a physical form again, as suggested by the Tale of Years.
And what did Sauron do as a spirit during all the years, decades, centuries, or millennia it took him to make a new physical body for himself? Maybe he concentrated only on making himself a new body. Maybe he roamed the world invisibly, telepathically encouraging Sauron worshippers and discouraging anti Sauron groups.
Obviously Sauron gained a degree of influence and/or control over many groups of Orcs, trolls, evil creatures, and mortal men in the last two millennia of the Third Age. It is assumed by readers that the various groups of "barbarians" who came from the east to attack Gondor, for example, were influenced by Sauron in one way or another to migrate west and attack Gondor.
Tolkien sometimes wrote that the other two wizards, the Blue Wizards, traveled to the east of Middle-earth to fight against Sauron's attempts to regain his influence, overlordship, and direct control of various lands in the east. Tolkien didn't make up his mind about much they succeeded or failed, but clearly by the time Sauron returned to Mordor he could have brought a large army of Sauron worshippers from the East as an invasion force if he wanted or needed to.
Sauron might not have needed an army to enter Mordor openly. Mordor had not been guarded by Gondor for centuries by then, and had even been controlled by the Nazgul for centuries, who presumably had formed armies of orcs and communities of human slaves in Núrn to feed the orcs.
See my answer to this question: Was Mordor inhabited between Sauron's defeat at the battle of the last alliance and his return?
Sauron was allready the monarch of Mordor, governing it from afar, when he entered it and openly proclaimed himself to be Sauron returned.
