Bem, pelo que me lembro, o Gollum chegou a ser ajudado por orcs, para fugir de Mirkwood, portanto não podemos descartar que ele não possa ter sido ajudado por orcs para entrar em Moria, mas minha teoria é:
Após a fuga da Floresta das trevas ele foi atrás do anel que estava do outro lado das montanhas(ainda), então talvez ele tivesse passado por Moria(meio improvável, mas possível), ou por um outro caminho de baixo das montanhas(que ele conhecia bem), então, ele pode ter avistado a comitiva quando saiu das montanhas, e os seguiu até Moria, onde para entrar, deve ter achado algum caminho dos orcs(que acho que não ficavam tendo que falar a senha da porta para entrar em Moria)e mesmo que tenha demorado para encontrar essa passagem dos orcs ele conseguiu alcancar a comitiva que ficou um tempo sem saber aonde ir (pois me lembro que o Gandalf ficou indeciso uma vez) então continuou atrás da comitiva, quando a sociedade foi atacada por orcs, não deve ter sido difícil pra ele se esconder, então, após a queda de Gandalf e da ponte quebrar, ele pode ter seguido os orcs que sairiam atrás da comitiva, por caminhos escavados pelos próprios orcs, depois, foi só seguir as trilhas e encontrar a comitiva novamente em Lórien
(não tenho certeza, mas tem uma parte, que os elfos de lórien contam que mataram os orcs que entraram em Lórien, e junto havia uma criatura, estranha que eles não mataram, pois não sabiam se era boa ou má, talvez isso possa comprovar que Gollum tenha ficado "amigo' dos orcs quando ficou preso por um loongo..tempo em Mordor)