Valinor as explained was the home of the Valar, Tolkien's term for the gods of Middle-earth. The sea to the west of the island was called Ekkaia, or the encircling sea; it surrounded both Valinor and Middle-earth.
Each of the Valar had their own region of the land where they resided and altered things to their desire. Yavanna, the goddess of nature, growth, and harvest, resided in the Pastures of Yavanna in the south of the island. Oromë, the god of the hunt, lived in the Woods of Oromë to the north-east of the pastures. The forest was home to many creatures which Oromë could track and hunt. Nienna, the lonely goddess of sorrow and endurance, lived cut off in the far west of the island in the Halls of Nienna where she spent her days crying, looking out to sea. Just south of the Halls of Nienna and to the north of the pastures there were the Halls of Mandos. Mandos, the brother of Nienna, was the god of the afterlife. All inhabitants of Middle-earth went to the Halls of Mandos should they happen to die, mortals and immortals alike (Tolkien's immortals could be killed although they did not die of old age) although it was said that in death as in life, they were separated. Also living in the Halls of Mandos was his spouse Vaire the weaver, who wove the threads of time.
To the east of the Halls of Mandos was the Isle of Estë, which was situated in the middle of the lake of Lórellin which in turn was situated to the north of the Gardens of Lórien (not to be confused with Lothlórien in Middle-earth which was created by the same Valar, Lórien also known as Irmo, the god of dreams). Estë and Lórien being husband and wife lived close together. To the north of this were the Mansions of Aulë the smith Valar who was spouse to Yavanna. In the north-east lay the Mansions of Manwë and Varda, the two most powerful Valar, also married. To the west of them stood the Two Trees of Valinor, Telperion and Laurelin. The entire great continent of Valinor was surrounded on three sides (excluding the north which was instead protected by ices flows) by a huge mountain range called the Pelóri mountains. In the extreme north-east, past the mountain range was the pass of Helcaraxë, a vast ice sheet which in the beginning, before Valinor was risen after the fall of Númenor in to the sky to prevent people from travelling there, joined the two continents of Valinor and Middle-earth. In the beginning, some Elves, tricked by the evil god Melkor passed along this pass to go back to Middle-Earth, among those was Galadriel who featured in the War of the Ring. Those who took this pass were not allowed back to Valinor for many years, but in the end pity was taken on them when Middle-earth began to fade and pass into the age of men and they were allowed to pass back to the Undying Lands of their own accord when they felt ready to do so.
Also, for a time before the ruin of Númenor, a long chain of small islands called the Enchanted Isles ran the full length of the east coast of the continent. These were created to prevent anyone, mortal or immortal, from reaching the land by sea.
After the destruction of Númenor, the Undying Lands were removed from Arda so that Men could not reach them and only the Elves could go there by the Straight Road and in ships capable of passing out of the Spheres of the earth. By special permission of the Valar, the Hobbits Frodo Baggins, Bilbo Baggins, and Samwise Gamgee were also permitted to go to Valinor, as well as Gimli the Dwarf.
It has been suggested that the concept was based off Hy Brasil, a mythical land that can reputedly be seen off the coast of Ireland for one day in every seven years.