Sauron's army contained a mixture of Orcs, Easterlings and Haradrim. From my understanding of the books and films the Orcs are created by Sauron and act as his slaves. So the Orcs don't have much of a choice. But what about the others?
Why were the Easterlings and Haradrim fighting for Sauron?
Orcs were not created by Sauron. They first appeared in the First Age, the work of the first Dark Lord, Morgoth, who Sauron served at the time. That said, Morgoth did not 'create' them either. Only Eru (Middle-Earth equivalent of God) was capable of creating life. Morgoth twisted other life of some sort into Orcs, though Tolkien spent his whole life wrestling over their exact origin.
The men of the east and south were loyal to Morgoth/Sauron, because they had known little else. His enemies in the west were the descendants of those who wanted to escape the Morgoth in the First Age and then met and fought alongside the Elves who were also fighting Sauron. There was very little opposition to him in other lands.
