23,000 years before the events told in the Lord Of The Rings, Iluvatar (God) sang the song of creation. Illuvatar wanted to create two new living beings—Elves and Men, both of which he called Children of Illuvatar. Elves (the Firstborn) were to be given life first, followed by Men (the Secondborn).
Illuvatar instructed his fourteen Valars (powerful gods) to create a new world in preparation for the coming of his children. These fourteen Valars created Arda (the world), which contained one large landmass, surrounded on all sides by seas. This was how Middle-Earth got its name—it was a landmass in the middle of Arda. The fourteen Valars (gods) each had his or her own field of specialised knowledge—one was specialised in wind, another in water, yet another in metal, etc. They used their knowledge to create all the complexities of Arda. When Arda was completed, all the Valars came down from their spirit plane to inhabit this new physical world. As I understand it, it was a one-way trip: the Valars could not go back up to their spirit plane. They would walk the lands of Middle-Earth as gods (that they properly were).
The 15th and last was a most powerful Valar named Melkor, who did not have any specialised knowledge, but who was decreed by Illuvatar to be the custodian of Middle-Earth. Melkor knew a little bit of everyone else’s specialised knowledge—somewhat like a jack of all trades but master of none. Using his little bit of knowledge in every field, he perverted the creation in all manners of little ways.
Melkor did not want to share Middle-Earth with the other Valars, so he battled and defeated them, and chased them all to a corner, north of Middle-Earth. The fourteen Valars were unhappy that they were hurdled into a tight corner, so they went and created a second landmass, west of Middle-Earth. This second landmass was called the Undying Lands. Middle-Earth and the Undying Lands were separated by sea, but with a finger landmass connecting the northern portions of both continents. At this point of the story, the geography of Arda had become very different from the original creation. (Two land masses now versus one previously.)
So the evil Melkor ruled the entirety of Middle-Earth, while the other 14 gods stayed in the Undying Lands.
In the meanwhile, the first Elves were beginning to stir in Middle-Earth. The first Elves arose from their assigned place of “birth”—a magical lake somewhere near the centre of Middle-Earth. The first Elves, who were born 3000 years before the beginning of the First Age, were treated horribly by Melkor. Some of the first Elves were re-shaped by Melkor into Orcs.
Imagine the horror that the 14 Valars felt when they realised that the Firstborn Children of Illuvatar would arise in the land corrupted and ruled by Melkor. Three Valars made secret incursions into Middle-Earth to convince the first Elves to migrate to the Undying Lands. The first Elves were suspicious of the Valars at first—understandably so, since the circumstances of their birth and early life had been harsh and cruel.
After much convincing, three Elven leaders organised three tribes to trek their way across the land to the western shores of Middle-Earth, where they could then set sail for the Undying Lands. Thus began The Great Journey of the Elves, which started 3000 years before the First Age and continued all the way till the end of the Third Age. (Some Elves stayed behind, refusing to leave Middle-Earth. These Elves were called The Unwilling.) Each of the three willing tribes took a different route when they came up against the obstacle that was the Misty Mountains. One tribe went through the mountain range, the other two went southwards, going around the obstacle instead of through it. Along the way, some Elves saw the beauty of Middle-Earth and decided to discontinue their journey to set up new Elven villages, such as Lothlorien.
The Elven population in Middle-Earth grew because those Elves who stayed behind married and beget Elven children, and also because the magical lake kept creating new Elves (???).
The Valars always kept the option open through the ages for these unwilling Elves to migrate to the Undying Lands. That is why you see in the movie these Elves that seem to be journeying somewhere (but we never quite knew where they were headed to).
But the story doesn’t end here.
Soon after the beginning of the First Age, Men appeared. Towards the end of the First Age, a great war took place, which saw Men helping the 14 Valars vanquish the evil Melkor once and for all. Melkor was killed, but Melkor’s servant, Sauron, managed to escape. The 14 Valars were very happy with the contribution of Men to Melkor’s defeat, and in gratitude created a new island in the sea (positioned in between Middle-Earth and the Undying Lands) called Numenor for these men to inhabit. The Men of Numenor were blessed with longer life spans than normal men. (In the EE of The Two Towers, Aragorn revealed to Eowyn that he was 87 years old, much to her shock. Aragorn was the last of the Numenors.)
But the Valars prohibited Men from sailing to the Undying Lands. Only the Elves were allowed to set foot there.
The Men of Numenor grew in power and ambition during the first half of the Second Age. Sauron poisoned the minds of these Numenoreans by whispering to them that immortal life could become theirs if they (the Men) ignored the prohibition and stayed in the Undying Lands. So an armada of ships sailed from the island of Numenor to the Undying Lands. When the men were about to step foot on the Undying Lands, the Valars punished men by having the sea rise up to swallow the ships and the island of Numenor. Numenor went under the sea; Tolkien’s version of Atlantis.
The Valars also disconnected the Undying Lands from the world of Arda. The Underlying Lands now ceased to become part of Arda. One could no longer sail via ship from Middle-Earth to the Undying Lands. The Undying Lands existed on a different plane of existence. The Undying Lands were not a spiritual plane—it still remained a physical world, but a physical world ripped from Arda. This marked the end of the Second Age.
During the Third Age, Elves who wanted to migrate to the Undying Lands could still do so. They could no longer use ordinary ships because ordinary ships cannot reach the Undying Lands. The Elves set up the port of Grey Havens, where special ships would take them “on a straight road” to the Undying Lands. When Galadriel, Elrond, Gandalf and Frodo set sail from the Grey Havens, this marked the end of the Third Age.