It has long been speculated that Middle-earth and Narnia could be two sides of the same map. The map of Middle-earth has the Great Sea in the west, Middle-earth itself in the middle, and barbarians (Easterlings) to the East. In Narnia, the situation is flipped - it has a Great Eastern Ocean, while to the west lie the mountains of the Western Wild, beyond which is the barbaric realm of Telmar. Both worlds are flat - Valinor lies on the western edge, and we see the Utter East in Dawn Treader - and, significantly, they were written by the great friends Tolkien and Lewis. So far, so obvious. What else can be said?
Dwarves
There are two different dwarven races in Narnia - Black Dwarfs and Red Dwarfs. In Middle-earth, there are seven; three feature in the stories (including the Longbeards, Durin's folk), while the other four appear only in a list - which states that they arose far to the east. The Fathers of the Dwarves awoke in pairs (except for Durin), and by the structure of the list, the easternmost pair were the fathers of the Blacklocks and Stonefoots. The connection of the Blacklocks with the Black Dwarfs of Narnia is almost irresistable.
Aslan refers to the dwarfs as the 'Sons of Earth' - in Arda, we know they were created from earth by the Vala of Earth, Aule. We also know that the Blacklocks and Stonefoots arose in the Orocarni Mountains - and the Lantern Waste of Narnia, where the stories all begin, lies on the eastern edge of a mountain range.
Jadis
If we ignore her purported otherworldly origin (and a good reason to do that will be discussed shortly), Jadis is a perfect fit for a Maia of Melkor's following. We know from the Ainulindale that Melkor has power over cold as well as heat (he accidentally created snow), but we never see Maia of Ice in his service - just fire. That could well be because his ice-themed followers were busy in the east. Significantly, before The Magician's Nephew was written, Jadis was said to have come from the north - the direction of both of Melkor's fortresses, Utumno and Angband.
It should also be noted that Narnia was protected from Jadis by a magic tree - and trees which are linked to the lives of their kingdoms are also found in Numenor and Gondor.
Hildorien & the Awakening of Men
In Middle-earth, the race of Men is known to have arisen in the far east, in a place called Hildorien. In Narnia, of course, humans first appear in the Lantern Waste, having travelled there from Earth - and the Lantern Waste is part of the eastern lands of the world, though it lies northwest of Narnia proper.
A tale is told - by Adanel of Hador to Andreth of Beor, and thence to Finrod of the Noldor - of the Fall of Man; of how men at first listened to the quiet voice of Iluvatar, but were drawn away by the wiles of Melkor. This suggests a key point: that, while the Eldar were under the care of the Valar, Men were the direct concern of Iluvatar Himself. There is a clear analogy here to Aslan, who is presented in Narnia as being God incarnate - not some messenger, but actually God.
Nurn
The easternmost named geographical location in Third Age Middle-earth is Nurn, in south-east Mordor, in the heart of which lies the Nurnen sea. In two of the three scripts of Middle-earth (the Sarati and Tengwar), vowels are represented by diacritics, or accents. If these were unwritten, Nurn becomes N-RN - which is also exactly how 'Narnia' would be written. The 'N-RN-N' Sea is simply 'Narnian'.
Of course, these lands are not actually remnants of Narnia - but if the Gondorians who first explored them had only fragmentary records to go on, naming the easternmost lands after the easternmost land they've heard of is entirely natural. (The same kind of thing happened in the real-world naming of Brazil - named for a mythical island in the Atlantic).
The Problem of Transmission
... is not actually a problem.
If Narnia is east of Middle-earth, and both actually existed, then the tales of Middle-earth can be said to have reached Tolkien by way of the Red Book of Westmarch - Bilbo's diary. Specifically, according to Tolkien, a copy of the Red Book, made in Gondor and bundled with Bilbo's 'Translations from the Elvish' (ie, the Silmarillion and associated works), was the source of Tolkien's translations.
That being so, we have to assume that the Chronicles of Narnia reached us in the same way - through being collected in Gondor and bundled with the other historical works.
That being so, there are aspects of Narnian history that must be simply invented - as, indeed, there are of the history of Middle-earth. The Lord of the Rings describes what Frodo saw on his journey to Valinor - a description which Sam (the last chronicler in the Red Book) must have drawn from elsewhere, since he has no way of knowing what Frodo actually witnessed. It's a literary invention - one of the few in the Red Book.
Narnia suffers the same problem. We know that the land of Narnia and its surroundings were completely destroyed at the end of The Last Battle - which means the final sections cannot have been witnessed by any living chronicler. Any events in the New Narnia, in particular, have no living witnesses. So where did they come from?
Well - religion, and hope. In Tolkien's world, there is an idea that, when the world has ended, Men (and possibly Elves) will join with Iluvatar to sing a new song, and create a new world - Arda Renewed, a world redeemed from the Fall. This is a pretty good description of the New Narnia - and the fact that all the 'Friends of Narnia' - all their legendary heroes - show up there strongly suggests a 'wrapping up of the story'.
There are several other things that 'how did it get here?' rules out. If we assume that all events actually taking place in Narnia were recorded, and that any trustworthy source from outside can write down what they experienced elsewhere, we can allow the entire text of The Lion, the Witch, and the Wardrobe through to The Silver Chair. What we do not have to accept is the accounts in The Magician's Nephew. The only 'reliable source' who has time to write anything down is Frank - and he knows nothing of the adventures of Digory and Polly in Charn. There is no opportunity for them to tell him, either - he simply made it up to account for the terrifying Maia Jadis.
'But wait!' I hear you cry. 'Professor Kirke knew the other Friends of Narnia!' Yes, he did - but none of them mention Charn, suggesting he never told them that story. And his only appearance after admitting he knows of Narnia takes place in The Last Battle - in the New Narnia, no record of which can have reached us.
The Timeline
If we propose that Narnia is in Arda, then we need to synthesise the timelines. There are two key events in Narnian history which can be used to fix it:
The creation of the world - or, more specifically, the arrival of Men in the world, the first rising of the Sun, and the awakening of both animals and plants.
The destruction of Narnia, in which all the known world is destroyed, right down to the sun and moon.
The Narnian creation has an obvious parallel - the first sunrise in Middle-earth, when Men awoke, and the seeds which had been in hibernation began to grow. The end of Narnia is rather more difficult - if we live in Middle-earth's future, then the actual end of the world has not yet happened.
However, there is a solution. Narnia is a flat world, as Middle-earth was - until the Fall of Numenor. We know that Valinor - the westernmost land - was removed from the circles of the world when it was made round. Could it be that the end of Narnia is actually the world being made round, and Narnia being destroyed - ripped entirely from the sphere of the world and, since it is not a Blessed Realm, being entirely crushed? An unidentified witness to most of the events of The Last Battle could have fled westward with the Chronicles, managing to reach the land that would remain in Arda - and, looking back, could have watched from the outside as the land simply disappeared, and the Sea was thrown back.
But there is another issue. The Fall of Numenor occured in the year 3319 of the Second Age - some 3900 years after the creation of the Sun. The official timeline of Narnia is 2555 years long - barely more than half the length. There are several possible explanations for this:
C.S. Lewis can't count - if we assume that Lewis constructed the timeline from references in the translated Chronicles, he may simply have gotten it wrong.
Narnians can't count - if, instead, the timeline is taken from the Chronicles, it could simply be wrong. Narnian history has enough conquests and falls that a few centuries could have gotten lost - but a full 1500 years seems a bit much.
Jadis can't count, or rather, didn't want to - was the Hundred Year Winter actually a Thousand Plus Year Winter? It seems something of a stretch, but it's possible.
Jadis messed with counting - we know from the example of Lorien that it's possible to muck about with time in Arda - what the Fellowship experience as around three days actually takes a month. If we read that as a 1:10 compression (ie, 30 days feel like 3), the Winter lasts a thousand years - leaving only 350 to be accounted for in chronicling errors.
This is one of the more tempting options - it doesn't rely on a huge mistake, but on a known ability that exists in the combined world. The main flaw is that the other nations - Calormen, Telmar, Archenland - were presumably outside Jadis' reach, and the difference would have become obvious. Unless of course they weren't beyond her reach - just beyond her Winter.
Narnians count differently - we know that in Tolkien 'miles are miles, and years are years' - but does that apply in Narnia? If a Narnian year was 18 months, that would make Narnia's timeline some 3850 years long. An even closer match can be found if we assume a year of 20 lunar cycles (a nice round number) - 560 days, or 1.533 solar years; this gives us a timeline 3917 years in length, which, allowing for uncertainty in the length of the First Age, is an exact match.
Alternately, we can combine this idea with the 'thousand year winter'; to make 3555 Narnian years equal 3900 solar years, we find a Narnian year lasting 400 days - another nice round number.
Ultimately, it doesn't matter which timeline theory is correct (though I prefer some combination of the last two) - what matters is that it could be correct. And I think this theory demonstrates that nicely.
"Those who would like to learn further about Numinor and the True West must (alas!) await the publication of much that still exists only in the MSS. of my friend, Professor J.R.R. Tolkien." - C.S. Lewis