The Blessed Realm
Valinor is the name for a large area on the continent of Aman in JRR Tolkien's fictional world of Arda. Whereas much of the action in his stories takes place in Middle-earth, much of the history behind the stories takes place in and around Valinor. The name Valinor comes from the Valar, the beings who founded it.
Originally, Aman was uninhabited. The Valar, who serve as the physical representations of various parts of the mind of Ilúvatar (Tolkien's creative force/universal power), originally dwelt at the Isle of Almaren, in the far east of Middle-earth, many ages before the start of the First Age. They were driven from Almaren by the rogue Vala Melkor, whose antagonism would go on to create the basis for the entirety of the conflict as detailed in all of Tolkien's major works. When he destroyed Almaren, the other Vala made for Valinor, and have remained there since. After the Elves came into the world in the far east of Middle-earth, the Valar decided that they should remove from the place of their birth to Valinor, lest they be corrupted or destroyed by Melkor and his minions. The Vala Oromë was sent to work this out with the first of the Elves, and many went with him. As the Elves aged, they split into three major groups; the Noldor, the Sindar, and the Teleri. Almost all Noldor and Sindar went to Valinor quite early on in Arda's history, but a large contingent of all three groups remained in Middle-earth to live what lives they could; they became known as the Avari. Eventually it became common practice for the eldest of the Elves, regardless of the original groupings, to sail by themselves or in small groups to Valinor, where they could live out their immortality in splendour with the Valar. This practice lead to Valinor being dubbed "The Undying Lands."
Elven splendour didn't always rule, as there were several attempts by various villains throughout the history of Arda who have tried their hand at invading its sanctity. Melkor, of course, being the chiefest among them. He, along with Aman native and all-around mutant freak spider Ungoliant partnered and invisibly invaded the city of Valmar, and succeeded in darkening the the Two Trees of Valinor, which at the time were the land's sources of light (the world outside of Valinor was otherwise still dark, but for the stars, at this point). This event brought about the end of the Years of the Trees and the beginning of the First Age. Further down the line, at the end of the Second Age, King Ar-Pharazôn of Númenor amassed a great fleet and, after having been corrupted by Melkor's lieutenant Sauron, sailed to Valinor with the intent of conquering it. Since the entire continent is protected by gods, it is needless to say that Ar-Pharazôn was unsuccessful, as he and his entire fleet were destroyed the moment he set foot on the shores of Tol Eressëa (the largest of the islands off the east coast of the continent). Númenor was also destroyed at that time, as punishment for Ar-Pharazôn's hubris. After that disaster, Valinor was removed from the world by the Valar, making it unfindable and inaccessible to everyone but the Elves, for whom the "straight road" was kept open, and to the souls of Elves and Men who had died in Middle-earth, though it's a toss-up as to how they managed to get there, even in spirit form, if the "straight road" was open only to the elves. (The souls of both slain Elves and dead Men went directly to the Halls of Mandos, where the Elves were judged and allowed to become corporeal again if the Vala Mandos deemed them worthy, and the souls of Men went to parts unknown; what became of the souls of Men was not ever specified other than that of Beren Erchamion, who, after being instrumental in defeating Morgoth (as Melkor came to be known), was allowed to reincarnate and live out a peaceful mortal life with his lover, Lúthien Tinúvial. There is some speculation that all souls go to Mandos and then points onward depending on their race in life, but I wasn't able to find verification of this anywhere.)
Facts and Figures
Of all the Elves in Tolkien's work, roughly half were born in Valinor, and nearly all that survived into the Fourth Age eventually migrated there. The most famous Elf born there would probably be Fëanor. Fëanor was also one of the first Elves to be exiled from Valinor, along with his sons, after the Oath of Fëanor incident just before the First Age, in which they assaulted the coastal settling of Alqualondë and made for Middle-earth in stolen ships to search for the Silmarils, recently stolen by Morgoth, who swore he was reformed after three full ages in exile; he was of course still the utmost evil in the world, but his ruse allowed him to gain the trust of the Elves. The entirety of the Noldorim was exiled shortly after, but all were eventually allowed to return; the last Noldor to return was Galadriel, whose valour during the War of the Ring and the aeons she spent in Middle-earth paid for her past misdeeds.
Other than Elves and Valar, very, very few of other races have been allowed to reach Valinor (Eärendil, a mortal man, notwithstanding because he eventually became immortal). They include three hobbits -- Bilbo Baggins, Frodo Baggins, and Samwise Gamgee, all of whom were Ringbearers in the War of the Ring -- and one dwarf, Gimli, son of Glóin, who was a member of the Fellowship of the Ring and the only dwarf to attain the title Elf-friend since long before the First Age; he and Legolas, a Sindar and member of the Fellowship of the Ring, became great friends during the War of the Ring. The three hobbits were allowed to live on Tol Eressëa after the War of the Ring, though Tolkien doesn't specifically mention where Gimli ends up (although it's probably a safe bet that he remained with his friend Legolas, who definitely came to dwell on the continent itself, as all Elves do). Also, the Istari, who were non-elven (they appeared as very tall, elderly men when they were corporeal) servants and apprentices of the Valar, came from Valinor, though only one of the five of them (Gandalf) is known to have returned. Finally, the Maiar (a group which includes the Istari, but with hugely different roles), who were kinds of lesser gods, also sprang up out of Valinor, though none were mortal and most of them perished either in service to or in opposition of Melkor and/or Sauron. The only Maia (other than Gandalf, an Istari) said to return was Melian, who in grief sailed west after the death of her elvish husband Thingol and the fall of Doriath, the forest realm they founded.
Geographically, Aman (and thereby Valinor) lay far to the west of Middle-earth, on the other side of the Great Sea. It is roughly shaped like the US state New Jersey, only continent-sized (though no quantitative specifications were ever given by Tolkien), and is the only land on the entire planet specified by Tolkien other than Middle-earth, which itself was a much larger continent.
On the geography:
- Valinor is protected from most conventional assaults by the Pelóri mountain range on its east coast. These mountains were raised by the Valar to prevent direct attacks made by Melkor.
- A small island called Tol Eressëa lies at the easternmost part of the continent. It was used, in lieu of ships, for shuttling groups of Elves from Middle-earth to Valinor by the Vala Ulmo, the spirit of the sea.
- Avathar, the uninhabited, narrow strip of land between the Pelóri and the sea, was in ancient times the dwelling of Ungoliant (who may have been the first being to ever inhabit the continent), and was where Melkor sought her out in his plot to darken the Two Trees.
- A long bay, the Bay of Eldamar, juts gently inland between Tol Eressëa and Araman, the northern shores.
- There are a number of different cities/settlements scattered across the continent, all within its central plain. Most are named for the Vala that inhabit them; the Halls of Nienna, Lórien, and the Halls of Mandos all lie toward the western coast, while Taniquetil, Valmar, Tirion, and Alqualondë are all near to the east. Tolkien never stated if any sailing was done from Aman to the eastern shore of Middle-earth (or from there to Aman's western shore), so it's a complete toss-up as to whether or not such a thing would be possible. In fact it's never specifically stated whether Arda is round or flat, hence the complete uncertainty about western Aman leading oversea to eastern Middle-earth.
* * * * *
After the events in The Lord of the Rings, nothing further about Valinor was written, though Tolkien gives us the impression that almost all Elves remaining in Middle-earth at that time eventually made their way west.