Fatti: A. A.a A._ e B._ sono proprietari in comune della particella xxx di Z._, che confina a monte con la particella yyy di proprietà di C._. Sui fondi sorgono due case contigue. Quella di C._ consta di un piano cantina, di un piano terreno e di un piano superiore. Fino al 1974 tale piano superiore era accessibile solo passando da una scala in granito posta nello stabile di A._ e B._; da allora esso è raggiungibile anche per mezzo di una scala in legno creata all'interno dell'edificio di C._. A.b Nell'ambito della procedura volta all'introduzione del registro fondiario definitivo a Z._, C._ ha notificato un diritto di passo pedonale tra il piano terreno e il piano superiore della sua casa lungo la scala in granito posta nello stabile di A._ e B._. Questi ultimi si sono opposti all'iscrizione della servitù. Con decisione 8 maggio 2002 la Sezione del registro fondiario e di commercio del Cantone Ticino ha accolto la notifica "ai sensi dei considerandi", ordinando l'iscrizione di un diritto di passo pedonale "limitato" - come risulta dai motivi della decisione - "a determinati bisogni particolari del fondo dominante a titolo integrativo del ricordato accesso interno, segnatamente trasporti, traslochi e passaggio di persone con difficoltà motorie". A.c Tale decisione è stata impugnata davanti al Pretore del Distretto di Lugano da C._, la quale ha postulato l'iscrizione di un diritto di passo pedonale senza limitazioni, e da A._ e B._, i quali hanno chiesto la reiezione della notifica di servitù. Statuendo con sentenze 22 dicembre 2003, emesse in luogo e vece del Pretore, il Segretario assessore ha accolto l'istanza di C._ e respinto quella di A._ e B._. Con decisione 11 aprile 2006 la I Camera civile del Tribunale d'appello del Cantone Ticino ha annullato le sentenze 22 dicembre 2003 e rinviato gli atti al primo giudice affinché verificasse l'esistenza di un interesse oggettivo da parte di C._ all'esercizio della servitù. Statuendo nuovamente (su rinvio) il 28 aprile 2008 il Pretore del Distretto di Lugano ha confermato la decisione 8 maggio 2002 della Sezione del registro fondiario e di commercio. B. In riforma della decisione pretorile 28 aprile 2008, con sentenza 29 febbraio 2012 la I Camera civile del Tribunale d'appello del Cantone Ticino ha ordinato l'iscrizione di una servitù di passo pedonale - senza limitazioni - sulla particella xxx in favore della particella yyy di Z._ "da esercitare tra il primo e il secondo piano sulla scala in pietra interna al fondo serviente". C. Con ricorso in materia civile 4 aprile 2012 A._ e B._ sono insorti al Tribunale federale contro la sentenza 29 febbraio 2012, chiedendo in sostanza di riformarla nel senso di non iscrivere a registro fondiario definitivo la predetta servitù di passo pedonale. In via subordinata essi hanno postulato il rinvio della causa all'autorità inferiore affinché pronunci una nuova decisione ai sensi dei considerandi. Con decreto presidenziale 1° maggio 2012 al ricorso è stato concesso l'effetto sospensivo. Con risposta 9 novembre 2012 C._ ha postulato la reiezione del ricorso sia in via principale sia in via subordinata. La Corte cantonale ha invece rinunciato a presentare osservazioni al ricorso. 