I was re-watching the fellowship recently and had this question. When the fellowship enters the mines of moria, the entrance is destroyed behind them, and Gandalf decides the only way forward is to move through the mines to the other side. But we also see later that Frodo catches sight of Gollum in the cave. Gandalf to is aware of this.
So how could Gollum have entered the mines ?
In the films we cannot be certain exactly when Gollum begins following the fellowship though the books and appendices surrounding the Lord of the Rings may help shed some further light on this. The dialogue exchange we receive is as follows:
'Frodo: There's something down there!
Gandalf: It's Gollum.
Frodo: Gollum?
Gandalf: He's been following us for three days.'
The Fellowship entered the Mines at 6pm on January 13th and escaped through the East gate at 1pm on January 15th TA 3019. If we are to assume this conversation took place on the evening of January 14th. The skirmish in Balin's Tomb and the flight across the Bridge of Khazad Dum resulting in the fall of Gandalf occur on January 15th so it must be assumed the Fellowship do not come upon Dwarrowdelf and the chamber of Mazarbul until the morning of January 15th. Therefore Gollum would have begun following them on January 11th, two days prior to them entering Moria. At this stage they would have been attempting the climb on Caradhras. Therefore we can assume that following Gollum's escape from Thranduil during the orc attack on Mirkwood he fled back to the Misty Mountains. It is possible that, knowing Sauron sought to find his ring, Gollum intended to track down Baggins himself and steal the ring back to spite Sauron who had tortured him for information on the rings whereabouts.
However this would seem to contradict other information. We know that Gollum tells Sauron two words, 'Shire, Baggins' which proves he knows exactly where the ring is or has a general idea if not knowing exactly where in the Shire Baggins is. It seems curious then that he did not attempt to steal the ring prior to this but also if he did intend to go after Baggins himself to reclaim the ring and spite Sauron then he would have had a head start on Legolas who himself has to travel across the Misty Mountains to get from Mirkwood to Rivendell where he reveals, during the Council of Elrond, that Gollum had escaped. It would seem reasonable to assume that Gollum would have been able to cross the Misty Mountains before Legolas could but instead he remains in the mountains. It is only once the Fellowship reach Caradhras that he begins pursuing them, albeit at a distance.
I assume Gollum simply follows the Fellowship in the hope of having the opportunity to recover the ring. He would notice that the party consisted of four hobbits with five other armed warriors protecting them and so for Gollum it probably would be easy enough for him to work out that the ring was in there possession. It would have been confirmed if he were to hear Frodo's surname spoken aloud at any point which would have continued his interest in them. The presence of Aragorn, Gandalf and possibly Legolas as well would have peaked his interest since all three were involved in his imprisonment at Mirkwood and Gandalf personally questioned him regarding the ring. I think its probable that Gollum tailed them to at least the West gate to be sure about their quest before deciding to pursue. It's also highly likely he witnessed the watcher in the water attack them and only after seeing them survive the encounter did he follow.
How did he get into Moria well we know for a fact that Gollum has been living in the Misty Mountains for a long time and if we are to assume he remained in his hideout beneath the goblin tunnels from the time of 'The Hobbit' he would have been living in the Misty Mountains for at least 60 years and it was implied he had been living there for a significant duration prior to his encounter with Bilbo. In 'The Return of the King' film we see a scene where he first enters the Misty Mountains through a crevice in the rock and so it would be highly likely that Gollum was aware of secret and far more inaccessible entrances to Moria and other sections of the Misty Mountains as he had been living and exploring there for so long. It is implied that Gandalf's knowledge of Moria was largely due to him having passed through with Bilbo and Thorin's company though in 'The Hobbit' we do not know it is Moria but it is implied to be connected as the company escape through the East gate whilst fleeing the goblins which is where Gandalf intends to lead the Fellowship once inside.
Gollum is also an especially skilled free climber which would allow him to traverse the rocky landscape far more easily than either the fellowship or the denizens of Moria itself. He could very well have climbed over the mountains and doubled back on himself through the East gate if necessary or simply waited for them to get there though i think it's far more likely he was able to climb through a crevice or even a gap in the destroyed ruin of the West gate to continue following them. Another interesting point to make is that Gollum is aware of secret entrances into Mordor despite supposedly being taken there simply for torture during the events preceding the Fellowship's expedition. It could very well be possible that the Ring somehow spoke to him and informed him of these passages and of Shelob. It may even have encouraged Gollum to venture to Shelob's lair at some time in an attempt to get him killed and allow the Ring to be one step closer to its master by being physically in Mordor. It is equally possible that the Ring was also aware that Moria was now overrun with goblins and orcs that were in service of Sauron and so could have shown Gollum other ways into Moria and the Misty Mountains in general to encourage him into a situation where he may lose the ring and put it into the possession of something that Sauron had far easier access to.
It's an interesting question and one we don't really have an answer to but I would assume he simply crawled through a gap or a tunnel that led him back into the mountains, he may even have gone through the door to the Goblin King's halls that Thorin's company fell through or just went down one of many tunnels he knew about having lived there for hundreds of years.
For more information on the times and dates of events the Fellowship were involved in please see here: http://tolkiengateway.net/wiki/Fellowship_of_the_Ring
Hopefully this helped with your question.
The first film only refers to Gollum intercepting the Fellowship as they passed through the mines, making no mention that they were specifically followed through the 'West Gate' / Doors of Durin, as due to his familiarity with the area Gollum should have been able to have entered the mine by an alternative route.
