He would have found an unguarded entrance
There is no reason to believe that Gollum entered Moria by the main east entrance (over the bridge that the Fellowship uses to leave Moria). As mentioned in the question, that would be very difficult, even for the stealthy Gollum, if the orcs kept any sort of watch on it.
Systems of caves and tunnels as large as Moria are unlikely to have one outlet in the east and one in the west. They would typically have several outlets of various sizes. Even if that was not the case, the dwarves would probably have created secret entrances (leading to narrow, easily defended passages) that they could use in emergencies (similar to the postern-door created by the Rohirrim in the Hornburg).
We know that Gollum was adept at finding his way into such places. We are told how he found his way into the caves where he eventually met Bilbo.
‘But as he lowered his eyes, he saw far ahead the tops of the Misty Mountains, out of which the stream came. And he thought suddenly: “It would be cool and shady under those mountains. The Sun could not watch me there. The roots of those mountains must be roots indeed; there must be great secrets buried there which have not been discovered since the beginning.”
‘So he journeyed by night up into the highlands, and he found a little cave out of which the dark stream ran; and he wormed his way like a maggot into the heart of the hills, and vanished out of all knowledge. The Ring went into the shadows with him, and even the maker, when his power had begun to grow again, could learn nothing of it.’
The Lord of the Rings Book One, Chapter 2: The Shadow of the Past
Page 54 (Houghton Mifflin Harcourt; Single Volume 50th Anniversary Edition)
Gollum would have entered Moria by finding a small unguarded entrance and then "worming his way in"