There are a number of times in Lord of the Rings where the "east" is mentioned -- the pirate ships, the slave-driven farms. And of course all of the peoples subservient to Sauron who come to fight Gondor and the West. Are there any maps of the East of Middle-earth, and what is out there?
There are plenty of maps of Middle Earth.
One such map is
The pirates you're talking about are the Corsairs of Umbar.
The LotR wikia states
The Corsairs of Umbar are a nation of Men, or corrupted Númenóreans, in Middle-earth known for their piracy of ships along the coasts of Gondor.
The slave driven farms I'm pretty sure are the people from Khand who fought for the Sauron Army.
An excerpt from the LOTR Wikia about Khand
Khand was the name of a land which lay to the south-east of Mordor and to the east of Near Harad. Almost nothing is known about Khand or its nomadic people. "Variags" (men of Khand) fought for Sauron's army, but nothing aside from their name was mentioned.
Pretty much I believe when they talked about East they are talking about lands to the far east of Middle-earth, more specifically ones to the east of Mordor.
There is a list of far eastern lands in the Wikia
- Sea of Helcar
- Sea of Rhûn
- Sea of Ringol
- Yellow Mountains
Another type of map I found was of Middle-earth and the Undying Lands.
For more sources about the information regarding Umbar
Gondor's power, however, eclipsed that of Umbar as the Third Age progressed, and at one point, perhaps around the time of Tarannon Falastur, Umbar acknowledged the sway of Gondor6.
↑ J.R.R. Tolkien, The Lord of the Rings, The Two Towers, "The Window on the West"
For more sources about Khand there are a few sources of information on Tolkien Gateway as well
According to Tolkien Gateway it states that Khand was South East of Mordor..
↑ J.R.R. Tolkien, Christopher Tolkien (ed.), Unfinished Tales, "The West of Middle-earth at the End of the Third Age" [map]
The Men of Khand were called Variags.5
↑ 2.0 2.1 J.R.R. Tolkien, The Lord of the Rings, The Return of the King, "The Battle of the Pelennor Fields"
Khand was under the influence of Mordor and supplied it with horses, and twice came into the history of Gondor: first in T.A. 1944 when the Variags together with the Wainriders attacked Gondor,5 and later during the War of the Ring when they fought at the Battle of the Pelennor Fields.
↑ J.R.R. Tolkien, The Lord of the Rings, Appendix A, "The Númenorean Kings", "Gondor and the Heirs of Anárion"
The East (and South) of Middle-earth, beyond the main published maps, was only ever mapped in the Ambarkanta, which was written in the 1930s and published in The Shaping of Middle-earth (HoME 4).
However, and as you can see, this mapping was very basic, and shows no geographical features aside from coastlines and major mountain ranges. It also pre-dates Lord of the Rings, so you're not going to see anything you know from the LotR maps on it, and it's also necessary to question exactly how valid it might be in terms of later work (and also later ages - this was pre-Drowning-of-Numenor and World-made-Round geography).
Karen Wynn Fonstad's Atlas of Middle-earth builds on this map to provide more detailed world maps, but of course they're not based on anything else in Tolkien canon so take them with the appropriately sized grain of salt.
David Day has also constructed his own maps in his own books, but his works are generally held in low regard.
For the second part of your question - why it's all subservient to Sauron - this is just a matter of geographic necessity. The West was where the remnants of the old Elven kingdoms were, it was visited by the Numenoreans, and the North-west in particular was the closest part of Middle-earth to Aman in the First and Second Ages, so Sauron is naturally going to expand in the opposite direction. See Letter 229:
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.
Also remember that in the Second Age Sauron had completely overrun Middle-earth with the exception of this North-western region; for most of that Age he had effectively "won". When Gandalf says (in Shadow of the Past) that "The Enemy still lacks one thing to ... cover all the lands in a second darkness" -- this was the "first darkness".
There is a complete Middle Earth map:
This one was published by Iron Crown Enterprises for the Middle Earth Role Playing game, under license by Tolkien Enterprises (1984). Tolkien Enterprises got the Rights from United Artists in 1976. AU, on its own, got the rights directly from JRRT in 1968.
This means that this map is "in canon", but not Tolkien-made.
Another one is the one pointed by DoctorWho22, which is again not Tolkien made, where you can see the second age (note that Middle Earth is still united to Undying lands, that Numenor is there and also Beleriand). A better quality image is
But note that the only one Tolkien-made map is the sketch pointed by Jimmy Shelter.
The East wasn't always under his fealty. Gondor settled Harad and Umbar, but they later rebelled in Gondor's civil strive over whom should be king of Gondor, etc.