For the full history of the Lord of the Rings, see The Return of the Shadow, The Treason of Isengard, The War of the Ring and Sauron Defeated. This is a very brief summary of some of the things that interested me from the above mentioned books. Each of the books covers a certain section of the Lord of the Rings:

The Return of the Shadow: The Long Awaited Party to The Bridge of Khazad-Dum
The Treason of Isengard: A lot of the stuff in the Return of the Shadow is rewritten with the final party. Other party ideas had included:

Frodo, Sam, Gandalf, Legolas, Erestor, Aragorn, Boromir, and Gimli.
An earlier idea was: Frodo, Sam, Merry, Faramond, Gandalf and Trotter (Return of the Shadow).
Another early idea was: Gandalf, Trotter, Frodo, Sam, Merry, Folco, Odo, Glorfindel, and Burin, son of Balin (the character to become Gimli, son of Gloin).(from the Return of the Shadow)
From The Return of the Shadow: Gandalf, Trotter, Frodo, Sam, Faramond, and Glorfindlel


The rest of the book goes from The Bridge of Khazad-Dum to The King of the Golden Hall. There is also stuff on the first of JRR Tolkien's maps.
The War of the Ring: The destruction of Isengard to The Black Gate Opens and the second of the main maps. This also include the formerly unpublished Epilogue.
Sauron Defeated: From the Black Gate Opens to the end of the Lord of the Rings and some other stuff on Numenor, including one of my favourite stories in the entire History of Middle-Earth, The Notion Club Papers.

The first idea was for Bilbo to have the adventures, though there was the problem of the fact that Bilbo was said to have had a long and happy life which made it hard for him to have had more adventures. The Hobbit, chapter 19: The Last Stage, page 284:
He took to writing poetry and visiting the elves; and though many touched their foreheads and said "poor old Baggins!" and though few believed any of his tales, he remained very happy to the end of his days, and those were extraordinarily long.
Other ideas included:

Having Bilbo get married and have one of his children have the adventure.
To have Bilbo run off for his second adventure after the Long Awaited Party speech. A variation of this was used in the Lord of the Rings, in that Bilbo does disappear at the end of the speech and does leave the Shire.

When Tolkien was first writing the Lord of The Rings, he decided to name Frodo, Bingo (full name Bingo Bolger-Bagins) instead. I believe that it was after a member of a family of toy bears. That lasted until about halfway through the Return of the Shadow. At that time there were various different names for the other hobbits in the party, ranging from Peregrin Boffin (Tolkien's original idea for Strider) to Odo Took and Marmaduke Brandybuck, so the idea of one Baggins, Brandybuck and Took was settled from the start. Sam Gamgee did not come in until later. Bingo Bolger-Baggins was at first decided to be Bilbo's son!! Strider was orginally called Trotter, and at first was a hobbit, though that was discarded by the first third of the second book, The Treason of Isengard.

In the Return of the Shadow (Book six of the History of Middle-Earth, and the first of the four books about the Lord of the Rings) Tolkien says that when Trotter first showed up in Bree, he had no idea of who he was and Tolkien had to find out as he was writing the story. Similar things have happened with other events and people in the Lord of the Rings, eg. Tolkien knew that there was going to be an adventure with an ent, though he thought that it was going to happen to Frodo. Immediately on having written it with Frodo, though, he decided that it was going to happen to Merry and Pippin. At first Treebeard was evil and in league with Sauron.
Quite a difference from the final version here!

At first though the idea of the Cracks of Doom were firmly there, Tolkien had no idea where they were. He thought that at first Sauron's ancient stronghold was in Mirkwood. It wasn't until later that he "found" Mordor was in the South-East, near to the land of Ond. At that time, Boromir's father was the king of Ond. It was't until later, indeed until the middle of the Treason of Isengard that the idea for the Stewards of Gondor came into existence.

There are two versions of the Hobbit, one of which has Gollum going to give Bilbo the Ring. Tolkien ran into trouble with this when he was writing The Lord of the Rings. As the Ring was taking on a more and more sinister aspect, having Gollum give away the Ring was less and less possible. To fix this Tolkien rewrote parts of the hobbit to suit the Lord of the Rings. The way he explains this in the Lord of the Rings is that Bilbo wrote the original version of the Hobbit as the Ring was taking effect, and when Frodo rewrote the Red Book of Westmarch he was unwilling to remove what Bilbo had put, so there were some copies made of the original.

The process in which Tolkien settled on a name for Aragorn was rather tortuous, though his first name for him was "Aragorn", included (in order, showing changes), Aragorn to Ingold to Elfstone, just to name a few of the changes. Finally late in the Treason of Isengard, the form Aragorn, son of Arathorn, was used, at least temporarily.

The song "Earendil the Mariner" sung by Bilbo in the chapter, Many Meetings, began life very similar to the song "Errantry". The two have the same style, though "Errantry" was much lighter in tone. Errantry can be found in the book The Adventures of Tom Bombadil.

Tolkien had some very interesting conceptions for the entry to Mordor, starting with only having one entrance, not called the Morranon, but Kirith Ungol, and very similar to Nan Dungortheb in Beleriand, with a ravine of giant spiders, larger than those in Mirkwood. In the earliest versions Sam is right next to Frodo, when Frodo was picked up by the orcs, and Sam tries to fight, but is trampled. This is in contrast to The Two Towers, when Sam has left Frodo, and hears the orcs, talking though he has left the area and only follows the orcs, and Gollum is nowhere in the area, while in the Treason of Isengard, in the drafts, Gollum is there with the orcs. Also in the drafts, they are not in the tower of the guard-tower on the far side of the mountains, but in Minas Morgul (strange thing: in the Treason of Isengard, Minas Morgul is spelled Minas Morgul as in the Lord of the Rings, while in Sauron Defeated, it is spelt Minas Morgol). Another thing, Frodo wasn't plundered, in the drafts, he still had the mithril-coat.
At this time, no meeting with Faramir, was planned or in existence.

Throughout the first half of the Treason of Isengard and all of the Return of the Shadow, Gondor was first referred to as the land of Ond or later as Ondor. In the second half of the Treason of Isengard, it became "Gondor" as in the Lord of the Rings.

In many ways the scene on Amon Hen was first written very similarly to the way it is in the Fellowship of the Ring. From the first the idea of Sam following Frodo to the boats and going off with him, leaving the rest of the Company of the Ring was used.

The beginning of the draft for The Departure of Boromir was written in almost the same words as in the Two Towers.
It was in the workings of the chapter, The Departure of Borormir, that Trotter first started to be referred to as "Aragorn" instead of "Trotter". It seems to me that this is when his name became Aragorn again.

For the chapter, The Riders of Rohan, the drafts are quite similar to the Two Towers. In this chapter is the first occurrence of Arathorn as the name for the father of Aragorn. The original idea for this chapter had Eomer on his way to attack the orcs, not returning from the attack.

In parts the workings for the chapter Treebeard are very similar to the Two Towers and in other parts very different.

At first in the chapter The King of the Golden Hall, there is no distrust of Gandalf, Aragorn, Gimli and Legolas at all nor any request to have them lay aside their weapons. This came later in the revisions along with the character Wormtongue who caused many of the problems within Rohan.

Much of the chapters up to The Voice of Saruman are very similar to the way they are in the Two Towers, with one of the main exceptions being the chapter Floatsam and Jetsam. In that chapter, the pipeweed had not come from the Shire, so there is no clue to what is happening in the Shire.

The chapter The Palantir, was very similar in most points to The Two Towers, except that at first the Palantir was smashed on the stairs of Orthanc and that the first drafts with it intact have Gandalf looking into it.

The first drafts of The Taming of Smeagol in the War of the Ring are very similar to the Two Towers, though they know that Gollum is following them before they even get down below the cliff. In the Two Towers, the first sighting and sound of Gollum after they left the Company was after they climbed down the cliffs at the edge of the Emyn Muil. It was when he was writing this chapter that Tolkien revised this passage in the Shadow Of the Past:
He deserves death.
Deserves it! I daresay he does. Many that live deserve death. And some that die deserve life. Can you give it to them? Then do not be to eager to deal out death in judgment. For even the very wise cannot see all ends.
The wording is slightly different as I have taken the quote from the Fellowship of the Ring and not from The War of the Ring (It is not fully there).

The Mumak. Even hobbits had heard of this majestic animal, as is shown in the poem Oliphaunt (The Lord of the Rings, pages 672-673):

The Lord of the Rings, pages 687-688:
"Ware! Ware!" cried Damrod to his companion. "May the Valar turn him aside! Mumak! Mumak!"
To his astonishment, and terror, and lasting delight, Sam saw a vast shape crash out of the trees and come careering down the slope. Big as a house, much bigger than a house, it looked to him, a grey-clad moving hill. Fear and wonder, maybe enlarged him in the hobbits eyes. But the Mumak of Harad was indeed a beast of vast bulk, and the like of him does not walk now in Middle-earth: his kin that live still now in latter days are but memories of his girth and majesty. On he came, straight towards the watchers, and then swerved aside in the nick of time, passing only a few yards away, rocking the ground beneath their feet: his great legs like trees, enormous sail-like ears spread out, long snout upraised like a huge serpent about to strike, his small red eyes raging. His upturned hornlike tusks were bound with bands of gold and dripped with blood. His trappings of scarlet and gold flapped about him in wild tatters. The ruins of what seemed a very war-tower lay upon his back, smashed in his furious passage through the woods; and high upon his neck still desperately clung a tiny figure - the body of a mighty warrior, a giant among the Swertings.

The chapter Of Herbs and Stewed Rabbit was first written very similarly to The Two Towers, except for the following: the two rabbits were a gift from Gollum and there was no encounter with the Men of Minas Tirith. In the next draft, the encounter with the Men of Minas Tirith was there, though their leader was not Faramir. Most of the text and the conversation is almost the same though.

The next chapter was originally called Faramir.This is the chapter A Window on the West. Almost all of it is in pretty much the same words as in the Two Towers, though said outside and with much interesting material on the languages used in Gondor.

In the chapter, Kirith Ungol (as it was spelt at that time), there were first many spiders, reminiscent of Mirkwood, then only one, at first called Ungoliant, not Shelob. The spider became Shelob during the section that later became known as The Choices of Master Samwise, when the two orc-patrols are meeting.

In all four books there is a lot of chronological tinkering to make sure that the four separate groups movements coordinate properly. By four I mean Frodo, Sam and Gollum as 1, Pippin and Gandalf as 2, Merry and King Theoden as 3 and Aragorn, Legolas and Gimli as 4. This can get very confusing as you read especially as the groups often change so that the members of one are often changed to be part of another. For help go to the calendar I have created for the years of the War of the Ring. At the time of writing the chapters in Dunharrow, Aragorn was there to meet Theoden and the Riders of Rohan and had not taken the Paths of the Dead, before they had arrived as in The Two Towers.

The chapter Minas Tirith is almost the same as in the Return of the King except for minor details in descriptions to the point of where Pippin and Gandalf leave Denethor in the hall. The later part of the chapter draft where Pippin meets the boy later to become Bergil, later to become the son of Berigond of the Guard of the Citadel, is really quite amusing. That draft was soon abandoned though.

The two parts titled Many Roads Lead Eastward are very interesting, in that at that time, Aragorn did not know where the Paths of the Dead were, and that Merry was at first to ride to Minas Tirith openly with the permission of King Theoden, not hidden under Dernhelm's (Eowyn's) cloak.

The part about Gandalf's defense of the Gates of Minas Tirith against the Lord of the Nazgul is similar in many ways to the Lord of the Rings and almost as powerful. (The War of the Ring pages 336-337)
The Black Captain ..... lifted again his hand crying aloud words of power and terror. Thrice the rams boomed. Thrice he cried, and then suddenly the gate as if stricken by some blast burst[?asunder], and a great flash as of lightning, burst and fell, and in rode the Lord of the Nazgul. But there waiting still before the gate sat Gandalf, and Shadowfax alone among the free horses of the earth did not [?quail] but stood rooted as an image of grey marble.
"You cannot pass," said Gandalf. "Go back to the black abyss prepared for you, and fall into nothingness that shall come upon your master."
The Black Rider [?lay for laid] back his hood and..... crown that sat upon no visible head save only for the light of his pale eyes. A deadly laughter [?rang] out.
"Old fool," he said. "Old fool. Do you not know death when you see it? Die now and curse in vain. This is my hour of victory."
And the same passage in the Return of the King:
Thrice he cried. Thrice the great ram boomed. And suddenly upon the last stroke the Gate of Gondor broke. As if stricken by some blasting spell it burst asunder; there was a flash of searing lightning, and the doors tumbled in riven fragments to the ground

In rode the Lord of the Nazgul. A great black shape against the fires beyond, he loomed up, grown to a vast menace of despair. In rode the Lord of the Nazgul, under the arch that no enemy ever yet had passed, and all fled before his face.
All save one. There waiting silent and still in the space before the Gate, sat Gandalf upon Shadofax, Shadowfax who alone among the free horses of the earth endured the terror, unmoving, steadfast as a graven image in Rath Dinen.

The first of the outlines for the story of Frodo and Sam in Mordor dates from the beginning of the entire story, when Frodo was still called Bingo Bolger-Baggins. At that time the scene on Mount Doom when the Ring is destroyed is essentially the same, with Gollum falling into the Cracks of Doom.
Later outlines of the same scene are substantially different, varying from Sam pushing Gollum into what was at that time called Saurons Fire Well and jumping in himself, to killing a Ring-wraith at the door to the cavern.
The second chapter jumps back to Cirith Ungol as it is called in the Lord of the Rings, though all the way through the History of the Lord of the Rings, it and all similar names were spelt with a "K" so it was spelt Kirith Ungol.

The idea that Frodo and Bilbo would go into the West with the bearers of the Elven Rings was in the story from the first and certainly there from the outlines after The Field of Cormallen (I am using the spelling from the Lord of the Rings).

Arwen was at first named Finduilas (Later this name was given to Faramir's mother). It was only in the chapter, Many Partings that the name Arwen came about for Elrond's daughter.

The names of some of the characters such as Trotter (Strider), Cosimo Sackville-Baggins (Lotho) and Barnibas Butterbur (Barliman) did not get changed until the third manuscript.

At first in the chapter The Scouring of the Shire, Frodo was given a more aggressive part than he had in the Lord of the Rings, though the words he spoke to Sam in what was at that time called In the Land of Shadow were already present:
I do not think it is my part to strike any blows again.
Many of the remarks given to Frodo in this first draft, were later given to Merry with no change in the wording, to show Frodo's more peaceful role in this chapter.

In the first draft for the Scouring of the Shire, the Party Tree, under which Bilbo made his farewell speech was still standing though in the later workings, the Party Tree was cut down.

Originally, Tolkien planned to have an epilogue to the Lord of the Rings in which Sam was answering his children's questions years later. This was never finished but the workings are present in Sauron Defeated.