[Turin Turambar]

Yet Frodo began to hear, or to imagine that he heard something else: like the faint fall of soft bare feet. It was never loud enough, or near enough, for him to feel certain that he heard it; but once it had started it never stopped, while the Company was moving. But it was not an echo for when they halted it pattered on for a little all by itself, and then grew still.

Clearly the footsteps are coming from Gollum. This means he followed them so it's only logical that he squeezed in to the west gate right before it was shut off by the watcher in the water. Perhaps in slipped in while the Fellowship was in shock and hid in the shadows until they began moving and then began to follow.