This issue has bothered me for some time.
Gollum is last seen peaking in on the Fellowship as they sleep outside the Chamber of Mazarbul in Moria. We next find him in a tree in the woods outside of Lothlorien. Much happens between points A and B.
As we all know, the Fellowship awakens, go into the Chamber, gets attacked, Gandalf brings the house down, the Fellowship flees, flies (you fools!) across the Bridge, which is destroyed behind them. Aragorn assumes command and keeps the company clipping along towards Celeborn's quarters. The Fellowship stops a few times, to look at a mere, to bandage the wounded, to wade and to sing. Despite all of this, they hope to make it to some place of safety before the orcs emerge from Moria to hunt them down.
So let's look at Gollum's possible route. We have to assume that he parts from the Company outside of the Chamber of Mazarbul, goes all the way back to where there is another passage, and starts his shadowing of the Fellowship anew.
Or did Gollum sneak past all Nine Walkers (including Aragorn) so to get ahead of them? Gollum obviously did not follow after the Ringbearer after Gandalf buries the Chamber, and so had to follow the Fellowship via another route. He could not have gone the 'main way,' out, as Gandalf remarks that, had the Fellowship done so, their exit from Moria would have been cut off via fire. Later, trolls bridge this fire/gap using slabs of stone. Was Gollum so extraordinary that he was able to make it past this trap that Gandalf and the orcs found so perplexing?
Or did he sneak past the Fellowship, and get on the other side of the Chamber, and so somehow stays in front of the Fellowship (on alert since the attack) as the Fellowship makes their way to the Bridge?
But let's say he is somewhere near the Fellowship as they make for the Bridge. He then must find another exit from Moria, as the Bridge is destroyed before he can use that way.
But let's assume that the Dwarves had built other ways out of Moria (though the Bridge was the main way), and that Gollum found and used one of these, which I assume were not guarded or were poorly guarded.
So assume Gollum escapes Moria somehow. He then actively pursues the Fellowship. Now, I'll concede that Aragorn is looking more forward than backward at this time, trying to get those thrust into his care to safety as quickly as possible. So let's say he doesn't see Gollum, who though trapped inside a mine for some time, is able to keep up with the Fellowship, moving as fast as possible to avoid orcs.
In daylight.
So, to recap: Gollum somehow gets past the greatest hunter of all time or finds an alternate route through a maze that almost stumps Gandalf, gets past a trap that would inhibit both Free People and orcs, gets across a chasm that, without a Bridge, keeps enemies from entering (or he finds an unguarded alternate passage), pursues the Fellowship unseen and travels rapidly despite suffering from deprivation and Yellow Face being in the sky.
Uh-huh.
My theory, based on what we read in the Books, is that the eagle
Deus ex machina flies Gollum out of Moria, setting him down later across the Nimrodel.
These are the 'wings' that we see behind the Balrog...
