Why were the people of Rhun and Harad allied with Sauron? Did they join him out of fear, or did Sauron say he would give them something if they joined him? I know the men of Dunland were angry at Rohan; did Rhun and Harad have something against Gondor?
This has origins in the Second Age, so I'm going to quote from Of the Rings of Power and the Third Age here (which, despite it's name, is a major source for the Second Age too):
In the east and south well nigh all Men were under his dominion, and they grew strong in those days and built many towns and walls of stone, and they were numerous and fierce in war and aimed with iron. To them Sauron was both king and god; and they feared him exceedingly, for he surrounded his abode with fire.
So it's a combination of both fear and worship, yes.
It's roots however go much deeper, back to the original awakening of Men and their original corruption by Morgoth, as is told in The Tale of Adanel (published in Morgoth's Ring).
Some say the Disaster happened at the beginning of the history of our people, before any had yet died ... But we were in haste, and we desired to order things to our will ... Then one appeared among us, in our own form visible, but greater and more beautiful; and he said that he had come out of pity.
You just know that this one isn't going to end well, don't you? So following this, Men turned from Iluvatar to the worship of Morgoth, started building temples and conducting human sacrifices, and died sooner and in great pain.
Eventually however some rebelled and escaped to the north-west of Middle-earth:
And they came at last to the land's end and the shores of the impassable water; and behold! the Enemy was there before them.
These were the ancestors of the Edain of Eriador and Beleriand, who in turn were the ancestors of the Numenoreans and the Northmen (e.g Rohirrim), but the others left behind retained their Morgoth worship, and were ancestors of the Haradrim and Easterlings, among others.
For the Second Age, Sauron's activity was mostly to the south and east, on account of the fact that the remaining Elven kingdoms were concentrated in the north-west, and that too was where the Numenoreans were most likely to visit.
At this point the whole "was Tolkien a racist" question is bound to come up, and the answer is a clear "no". There is ample evidence of his opinions in his Letters, including statements such as "that ruddy little ignoramus Adolf Hitler", "the wholly pernicious and unscientific race-doctrine" and "the treatment of colour nearly always horrifies anyone going out from Britain".
Tolkien himself stated in Letter 229) his reasons which correspond with those I have given above, and I'll quote:
The placing of Mordor in the east was due to simple narrative and geographical necessity, within my 'mythology'. The original stronghold of Evil was (as traditionally) in the North; but as that had been destroyed, and was indeed under the sea, there had to be a new stronghold, far removed from the Valar, the Elves, and the sea-power of Númenor.
In addition to the existing excellent answer, I want to point out that Appendix A makes clear that throughout its history Gondor was at war on an off with Harad and Rhûn. Those people would be predisposed to Sauron ("the enemy of my enemy is my friend").
Morgoth/Malkor was the most powerful of the Valar. Only Eru (God in Tolkien's mythology) was more powerful. During the song of creation Eru led the Valar and Maiar joined in. Malkor sang with pride and disharmony trying to outdo or at least equal Eru by forming his own creation. After this disharmonic singing reality was tainted. Through various forms of twisting these groups of humans by playing upon his song of discord, his show of power, time spent with them, and his snakes tongue he made these groups worship him as the true god. During all of this Sauron was a Maiar that served as Malkors General. After Malkors defeat when Sauron took up the job of amassing his own forces he used this knowledge of those civilizations and his history their plus their already negative views of the other humans and races from their time fighting for Melkor to convince them Melkor had returned or even that he himself was Melkor returned and they quickly fell in line behind their 'god' again