The earliest map that still survives in Tolkien's papers is a very rough pencil sketch of the world in the First Age. It shows Utumno, Valinor, the locations of the two Lamps, and a rough outline of Beleriand. He probably drew it in 1918-19, while he was working for the Oxford English Dictionary after leaving the Army. It's on a page of the manuscript for one of the stories in the Book of Lost Tales.
Throughout his writing career, Tolkien would continue this practice of scribbling small sketch maps in corners of his manuscripts or on scrap pieces of paper. It helped clarify his thoughts and keep clear in his mind the geography of the story he was writing.
The first detailed map he created was of Beleriand. This was drawn in about 1926, on three sheets of paper. The central sheet is very elaborate, drawn using pencil, coloured crayon and three different colours of ink. The two other sheets, extending the map east and west, were drawn more hastily in pencil only. After its initial creation, he amended the map multiple times: crossing out or and changing names, erasing terrain features and re-drawing them, and so forth. It was clearly a working document.
About ten years later, in the mid-1930s, he re-drew this map incorporating all the amendments into a new, neat copy. This version of the map was drawn in pen on four sheets of paper pasted together. Like the first map, however, he would subsequently make multiple changes and amendments to this version. It is this map that Christopher Tolkien re-drew in the 1970s and published in the 1977 Silmarillion.
The 1930s map of Beleriand
Also in the 1930s, Tolkien wrote a short essay he titled Ambarkanta: The Shape of the World. It is six pages long, and is accompanied by five maps and diagrams. It describes the form Arda was created in, as a flat world floating in the centre of a globe of air and water encased in crystalline walls, and also describes the change to a round world after the 'Cataclysm' when Númenor was destroyed. Two sketch maps show the world in the early First Age (when Melkor still dwelled in Utumno), and after the war between Melkor and the Valar when he was captured and brought to Aman as a prisoner.
The second map shows the continents of Middle-earth looking vaguely like those of our own world (Europe, Asia, Africa) plus a large and mysterious southern continent, and Aman and the 'Burnt Lands of the Sun' in the far West and East respectively. Beleriand is marked, but there is nothing but blankness to the east of it.
The two ‘Ambarkanta’ maps of the First Age
It seems that the next detailed set of maps Tolkien drew were those for The Hobbit, also in the early to mid 1930s. In the published book there are two of these: Thror's Map of the Lonely Mountain itself, which is presented as an actual item in the story, the map the dwarves use; and the Wilderland Map printed at the end of the book. Both began as sketch-maps Tolkien created while he was writing the book, and went through several versions before reaching their final published form.
There are some hints that Tolkien originally intended to set his story in Beleriand shortly after the final defeat of Morgoth. Mirkwood was to be Taur-nu-Fuin, the Withered Heath was Anfauglith, and the Lonely Mountain was somewhere in the region of the Hill of Himring. However he quickly decided, while still writing the first chapters, to set the story instead long after the events of the First Age and in a different part of Middle-earth. This meant that the maps he created were filling in what had previously been the blank area east of Beleriand.
Early draft of the Wilderland map
Tolkien began writing The Lord of the Rings around Christmas 1937, and would continue to write it, with long intermissions lasting up to a year or more, over the next 15 years. As usual, the process of writing was accompanied by multiple small sketch maps doodled in corners of the manuscript or on the back of re-used scrap pieces of paper. For example, he drew an outline of the town of Bree showing its relation to the crossroads and the nearby hillside.
The first detailed map created at this time was of the Shire, begun probably early in 1938. It went through three subsequent versions, each showing differing amounts of detail and at different scales. In 1943 Tolkien asked his son Christopher, then aged 18, to re-draw the map of the Shire in a neat version, using coloured pencils and chalks. He was apparently very impressed by his son's work, but unfortunately the map, though beautiful, was too complicated to be printed at an affordable cost. Therefore in about 1952 Christopher re-drew the map in a simplified black-and-white ink version. This was printed in The Fellowship of the Ring.
Early sketch-map of the Shire
By late 1939 Tolkien had taken the story as far as Rivendell. At about this time he took the map of Wilderland he had published in The Hobbit, and took another sheet of paper and sketched out what lay south of that map. It is at this point that the locations of Moria, Rohan and Fangorn Forest first emerged.
At some point after this, perhaps in 1940 or 1941, Tolkien began work on what is usually thought of as the definitive map of Middle-earth. This began as two sheets of paper glued together, and covered the world from the Shire in the top left to Mordor (or 'Mor-dor' as it was initially written) in the bottom right. At some point soon after this, he took three more sheets of paper and glued them onto the top and left edges to extend the map further to the north-west, to include the coasts. At this point he made the connection to his earlier map of Beleriand, with a couple of islands off the coast of Third Age Middle-earth which correspond to the highest hilltops of First Age Beleriand.
This map was, as usual, a working document which was amended multiple times. In fact, Tolkien went so far as to paste over a new sheet of paper in the area around Gondor (‘Ond' as it was called on the map) to make further corrections.
A composite image of the first full Middle-earth map, which was drawn on multiple sheets of paper glued together.
In 1943, at the same time Christopher Tolkien drew the map of the Shire, Tolkien asked him to draw a neat version of the Middle-earth map as well. As with the Shire map, Christopher had to re-draw this in 1952/3 so it could be printed in the books. This is why the map in The Lord of the Rings is signed 'CJRT'.
The final detailed map is the one in The Return of the King depicting the area around Gondor and Mordor. This was a collaboration by JRR and Christopher Tolkien, created in a rush in 1953 in order to be published in the book.
After publication, Tolkien treated the maps as 'frozen' and thus definitive. Christopher Tolkien noted in Unfinished Tales that he had become aware of some errors in his maps compared to his father's original intentions, and he took the opportunity in that book (in 1980) to correct those of them which could easily be changed, such as the location of the Ice Bay of Forochel.