Fatti:
A. Il 30 luglio 2010 il Procuratore pubblico del Cantone Ticino ha emesso un decreto di accusa nei confronti di A._, ritenendolo autore colpevole di falsità in atti formati da pubblici ufficiali ex art. 317 del Codice penale svizzero del 21 dicembre 1937 (CP; RS 311.0) per aver attestato, in un rogito relativo alla compravendita di un fondo, che l'acquirente aveva dichiarato di conoscere la lingua italiana, quando in realtà né la parlava, né la comprendeva.
Il procedimento è sfociato nella condanna del notaio a 90 aliquote giornaliere di fr. 250.-- ciascuna, sospesa condizionalmente per un periodo di prova di due anni, confermata in via definitiva dal Tribunale federale con sentenza 6B_662/2011 del 19 luglio 2012.
B. Preso conoscenza di tale condanna, con decisione dell'8 ottobre 2012 la Camera per l'avvocatura e il notariato del Tribunale d'appello del Cantone Ticino ha ritenuto che la falsità in atti commessa per dolo o dolo eventuale costituisce un atto contrario alla dignità professionale e quindi decretato nei confronti di A._ la cessazione dall'esercizio del notariato.
La misura, presa sulla base dell'art. 25 della legge ticinese sul notariato del 23 febbraio 1983 (LN; RL/TI 3.2.2.1), è stata in seguito confermata dalla Commissione di ricorso sulla magistratura, con sentenza del 30 novembre 2012. Anche quest'ultima ha infatti constatato che la condanna inflitta ad A._ ha comportato il venir meno di uno dei requisiti previsti per l'ammissione all'esercizio del notariato e che all'autorità competente non restava pertanto che decretarne la cessazione.
C. Con ricorso in materia di diritto pubblico del 16 gennaio 2013, A._ ha impugnato il giudizio di detta Commissione davanti al Tribunale federale, chiedendone l'annullamento.
Chiamate ad esprimersi, la Commissione di ricorso sulla magistratura e la Camera per l'avvocatura e il notariato hanno comunicato di non avere nessuna osservazione da formulare.

Diritto:
1. 1.1 Diretto contro una decisione finale (<ref-law>), il ricorso concerne una causa di diritto pubblico (<ref-law>) che non ricade sotto alcuna delle eccezioni previste dall'<ref-law> ed è stato presentato in tempo utile (art. 46 cpv. 1 lett. c in relazione con l'<ref-law>) dal destinatario della pronuncia contestata, con interesse al suo annullamento (<ref-law>). Conformemente all'<ref-law> (disposto che concretizza l'<ref-law>; sentenza 2D_71/2008 del 9 marzo 2009 consid. 3.1), la Commissione di ricorso sulla magistratura, la cui competenza è in casu sancita dall'art. 131a LN, dev'essere inoltre considerata un tribunale superiore: ovvero un'autorità giudiziaria che, negli ambiti che le competono, ha giurisdizione su tutto il territorio cantonale e non sottostà a nessun'altra autorità giudiziaria (<ref-ruling> consid. 4.1 pag. 97 seg.; sentenza 2C_557/2009 del 26 aprile 2010 consid. 3).
Come emerge dall'art. 85a della legge cantonale sull'organizzazione giudiziaria del 10 maggio 2006 (LOG; RL/TI 3.1.1.1), cui fanno riferimento il messaggio del Consiglio di Stato n. 6217 del 12 maggio 2009 e il relativo rapporto del 30 settembre successivo, che hanno portato all'adozione dell'art. 131a LN senza modifiche, le decisioni di questo organo non sono in effetti ulteriormente appellabili. Costituito da un Presidente, due membri e due supplenti eletti dal Gran Consiglio, esso non risulta inoltre essere sottoposto gerarchicamente a nessuna autorità giudiziaria superiore.
1.2 Sempre in questo contesto occorre d'altra parte osservare che - a differenza di quanto sostiene il ricorrente, con rinvio agli <ref-law> e 6 n. 1 CEDU - l'indipendenza della Commissione di ricorso sulla magistratura non può nemmeno essere messa in discussione richiamandosi al fatto che in detto messaggio il Consiglio di Stato aveva rilevato che la designazione della stessa quale autorità di ricorso contro le decisioni della Camera per l'avvocatura e il notariato fosse nelle sue intenzioni una misura di natura provvisoria, presa in attesa della revisione totale della legge sul notariato.
Benché concepita quale soluzione transitoria, la designazione della menzionata Commissione quale autorità di ricorso è infatti chiaramente prevista dall'art. 131a LN, norma di legge in senso formale entrata in vigore a tempo indeterminato scaduti i termini di referendum, ed è pertanto conforme all'<ref-law> che - analogamente all'art. 6 n. 1 CEDU, la cui applicazione alla fattispecie non deve essere ulteriormente approfondita - garantisce ad ognuno il diritto d'essere giudicato da un tribunale fondato sulla legge, competente nel merito, indipendente ed imparziale (<ref-ruling> consid. 3.3 pag. 133; <ref-ruling> consid. 2.1.2.1 pag. 34 seg.; <ref-ruling> consid. 4.1 pag. 198 seg.).
Sotto i profili evocati, l'impugnativa è quindi di massima ammissibile quale ricorso in materia di diritto pubblico.
2. 2.1 Con ricorso in materia di diritto pubblico può essere fatta valere la violazione del diritto federale (<ref-law>), nozione che include i diritti costituzionali dei cittadini (<ref-ruling> consid. 3.1 pag. 447). Salvo che per i casi citati dall'<ref-law>, non può invece essere censurata la violazione del diritto cantonale. È però sempre possibile fare valere che l'errata applicazione del diritto cantonale da parte dell'autorità precedente comporti una violazione del diritto federale e, segnatamente, del divieto d'arbitrio (<ref-ruling> consid. 2.3 pag. 466).
2.2 Il Tribunale federale applica d'ufficio il diritto federale (<ref-law>). Nondimeno, tenuto conto dell'onere di allegazione e motivazione posto dall'<ref-law>, esamina di regola solo le censure sollevate (<ref-ruling> consid. 1.1 pag. 104 seg.). Esigenze più severe valgono inoltre in relazione alla violazione di diritti fondamentali; censure in tal senso possono essere infatti trattate unicamente se sono state sollevate e motivate in modo preciso (<ref-law>; <ref-ruling> consid. 2.2 pag. 246; <ref-ruling> consid. 1.4.2 pag. 254). Anche in caso di asserita violazione del divieto d'arbitrio, è quindi necessario che il ricorrente esponga le sue critiche in maniera chiara e circostanziata (<ref-ruling> consid. 7.1 pag. 51).
2.3 Per quanto riguarda i fatti, il Tribunale federale fonda il suo ragionamento giuridico sull'accertamento svolto dall'autorità inferiore (<ref-law>). Esso può scostarsene se è stato eseguito in violazione del diritto ai sensi dell'<ref-law> o in modo manifestamente inesatto, ovvero arbitrario, profilo sotto il quale viene esaminato anche l'apprezzamento delle prove addotte (<ref-ruling> consid. 4.2 pag. 560).
Il gravame, di natura prevalentemente appellatoria, rispetta solo in parte i requisiti esposti. Per quanto siano disattesi, esso è pertanto inammissibile.
3. 3.1 La procedura trae origine dalla decisione dell'8 ottobre 2012 con cui la Camera per l'avvocatura e il notariato del Tribunale d'appello del Cantone Ticino ha considerato che la falsità in atti commessa dal notaio A._ costituisce un reato intenzionale contrario alla dignità professionale ai sensi dell'art. 21 e 25 della legge ticinese sul notariato e di conseguenza decretato nei suoi confronti la cessazione dall'esercizio del notariato.
Per quanto qui di rilievo, le due norme menzionate hanno il seguente tenore:
Art. 21 Requisiti
1 Il candidato in possesso del certificato di capacità, che intende esercitare il notariato, deve presentare istanza al Tribunale di appello.
2 Per essere ammesso all'esercizio del notariato, il candidato deve:
1. ...
2. non essere stato condannato o non avere in corso procedimenti penali per reati intenzionali contrari alla dignità della professione;
2. non essere stato condannato o non avere in corso procedimenti penali per reati intenzionali contrari alla dignità della professione;
... 3 Il Tribunale di appello, accertata l'esistenza dei requisiti che precedono, dichiara l'istante ammesso all'esercizio del notariato nel Cantone, gli rilascia il decreto di nomina e il diploma d'autorizzazione e fa analoga pubblicazione nel Foglio ufficiale.
Art. 25 Casi di cessazione
1 Cessa dall'esercizio il notaio:
1. ...
2. ...
3. ...
4. ...
5. quando sia stato condannato per reati intenzionali contrari alla dignità della professione;
5. quando sia stato condannato per reati intenzionali contrari alla dignità della professione;
... 2 Spetta al Tribunale di appello di accertare d'ufficio la cessazione dell'esercizio del notariato quando esistono i motivi indicati nel presente articolo. Il decreto sarà immediatamente pubblicato nel Foglio ufficiale. Il Consiglio di disciplina notarile e l'Ordine dei notai segnalano al Tribunale di appello eventuali motivi di cessazione.
3.2 Adita successivamente alla Camera per l'avvocatura e il notariato, la Commissione di ricorso sulla magistratura ha da parte sua confermato la legittimità del provvedimento in discussione. Chiamata ad esprimersi sulla critica secondo cui, in luogo della revoca amministrativa, le autorità avrebbero dovuto adottare unicamente una delle misure disciplinari previste dall'art. 127 LN, essa ha in effetti considerato che - una volta preso atto del fatto che la condanna inflitta al ricorrente concerneva un reato intenzionale contrario alla dignità professionale - non restava che procedere nel senso indicato dall'art. 25 LN.
4. Nell'impugnativa presentata davanti al Tribunale federale il ricorrente sostiene nuovamente che, invece di decidere una "revoca amministrativa", secondo l'art. 25 LN, le autorità cantonali avrebbero dovuto limitarsi a ordinare una "revoca disciplinare" o un'altra misura disciplinare, in base al titolo VI della LN, in modo da garantirgli una decisione conforme al principio della proporzionalità. In questo contesto, rileva quindi che la Commissione di ricorso sulla magistratura avrebbe trovato il sistema di interpretare e applicare "nel peggior modo possibile" la legge notarile ticinese, giungendo a una decisione arbitraria.
4.1 Confrontato con una critica d'arbitrio, il Tribunale federale annulla la sentenza impugnata per violazione dell'<ref-law> unicamente se l'istanza precedente ha emanato un giudizio che appare - sia a livello di motivazione che di risultato - manifestamente insostenibile, in aperto contrasto con la situazione reale, gravemente lesivo di una norma o di un principio giuridico chiaro e indiscusso oppure in contraddizione urtante con il sentimento di giustizia e d'equità (<ref-ruling> consid. 7.1 pag. 51 e 132 III 209 consid. 2.1 pag. 211 con ulteriori rinvii).
4.2 Come già visto in precedenza, l'assenza di una condanna per reati intenzionali contrari alla dignità della professione - di cui verrà detto più precisamente nel considerando successivo - costituisce una condizione esplicita per l'ammissione all'esercizio del notariato (art. 21 cpv. 2 cifra 2 LN); dal testo di legge emerge altrettanto chiaramente che una simile condanna comporta la cessazione dall'esercizio dell'attività di notaio (art. 25 cpv. 1 cifra 5 LN), la quale deve essere accertata dal Tribunale d'appello (art. 25 cpv. 2 LN, il cui tenore viene in seguito ripreso anche dall'art. 124 LN).
Tenuto conto del quadro legale appena decritto, la decisione di decretare nei confronti del ricorrente la cessazione dell'esercizio del notariato in luogo di una "revoca disciplinare" o di un'altra misura disciplinare, che sarebbe comunque di competenza del Consiglio di disciplina notarile e non della Camera per l'avvocatura e il notariato (art. 126 segg. LN), risulta pertanto tutt'altro che arbitraria.
Come ammesso dal ricorrente stesso, occorre d'altra parte osservare che la legge sul notariato non distingue affatto espressamente tra "revoca amministrativa" e "revoca disciplinare", ragione per cui l'agire delle autorità cantonali non può essere risultato di una grave lesione di detta legge, e perciò di arbitrio, nemmeno per questo motivo.
4.3 Nel medesimo tempo, l'arbitrio non è però dimostrato neanche in relazione alla sussunzione alla fattispecie specifica del concetto di "reato intenzionale contrario alla dignità della professione" giusta gli art. 21 cpv. 2 cifra 2 e 25 cpv. 1 cifra 5 LN.
Nel giudizio impugnato - dal quale emergono in maniera chiara i motivi su cui l'autorità fonda il suo ragionamento, e che non lede pertanto il diritto di essere sentito del ricorrente (<ref-ruling> consid. 4.1 pag. 88) - la Commissione di ricorso ha dapprima ricordato la ratio legis dell'art. 25 cpv. 1 cifra 5 LN, sottolineando in particolare la necessità di un intervento da parte dell'autorità superiore in tutti quei casi in cui comportamenti di rilevanza penale facciano dubitare in modo serio dell'idoneità etico-professionale del candidato o del notaio già ammesso all'esercizio della funzione.
Riferendosi alle argomentazioni sviluppate dalla Camera per l'avvocatura e il notariato - che già aveva concluso che una violazione dell'<ref-law>, commessa in stretta relazione con lo svolgimento della funzione di notaio e nelle modalità emerse durante la procedura penale, raffigura senz'altro un atto contrario alla dignità professionale del notaio stesso - ha quindi esplicitamente rilevato di condividerle.
Lungi dal risultare insostenibili (nel medesimo senso, si vedano <ref-ruling> consid. 6.1 pag. 427 seg. e le sentenze 2C_119/2010 del 1° luglio 2010 consid. 2.4 segg. risp. 2C_183/2010 del 21 luglio 2010 consid. 2.4 seg.), dette argomentazioni non vengono realmente messe in discussione dal ricorrente. In luogo di confrontarvisi, come la formulazione di una critica d'arbitrio avrebbe richiesto (<ref-law>), egli si limita in effetti a sottolineare il tempo trascorso dai fatti rimproveratigli e la condotta professionale da lui nel frattempo tenuta.
Anche simile motivazione non dimostra in ogni caso l'arbitrio nell'applicazione del diritto cantonale. Così argomentando, il ricorrente non si avvede in effetti del fatto che per l'art. 25 LN determinanti non sono gli aspetti da lui evocati - legati non da ultimo al tempo necessario per giungere a un giudizio penale definitivo - quanto piuttosto la gravità del comportamento penalmente rilevante tenuto dal notaio stesso che, proprio anche in ossequio dell'invocato principio della proporzionalità, è stato nella fattispecie già oggetto di attento esame da parte dell'autorità di revoca (giudizio della Camera per l'avvocatura e il notariato, consid. 2 seg.; <ref-ruling> consid. 6.1 pag. 427 seg. con ulteriori rinvii).
4.4 Una volta giunta ad ammettere la sussistenza di un "reato intenzionale contrario alla dignità della professione", la Commissione di ricorso poteva infine pure lecitamente considerare che non restasse nella fattispecie altro che confermare la cessazione amministrativa dell'esercizio del notariato, decretata originariamente dalla Camera per l'avvocatura e il notariato.
Dati gli estremi per l'applicazione dell'art. 25 cpv. 1 cifra 5 LN, di cui occorre per inciso dire che il ricorrente non chiede comunque nessun controllo accessorio, non vi è infatti spazio né per valutare diversamente i fatti alla base del giudizio penale, né per considerare aspetti specifici ritenuti rilevanti dalla persona toccata dal provvedimento (riguardo agli art. 8 cpv. 1 e 9 della legge federale del 23 giugno 2000 sulla libera circolazione degli avvocati [LLCA; RS 935.61] e agli art. 8 cpv. 1 e 2 in relazione con l'art. 20 dell'abrogata legge ticinese sull'esercizio delle professioni di fiduciario, che hanno struttura comparabile alle norme della legge ticinese sul notariato, cfr. le seguenti sentenze: <ref-ruling> consid. 6.1 pag. 427 seg.; 2C_955/2010 del 6 aprile 2011 consid. 5.2; 2C_183/2010 del 21 luglio 2010 consid. 2.6 e 2C_119/2010 del 1° luglio 2010 consid. 3).
Anche in questa sede può tuttavia essere fatto rinvio all'art. 27 cpv. 1 cifra 2 LN, da cui risulta che, una volta eliminata dal casellario giudiziale, la condanna subita non costituisce di principio più un ostacolo alla riammissione all'esercizio delle funzioni di notaio (in questo senso, cfr. il rapporto della Commissione della legislazione sul messaggio n. 5809 del Consiglio di Stato del Canton Ticino che, a pag. 20, fa espresso rinvio all'<ref-law>). Datene le condizioni, il ricorrente potrà pertanto inoltrare un'istanza di riammissione.
5. Per quanto precede, nella misura in cui è ammissibile, il ricorso va respinto, poiché infondato. Le spese giudiziarie seguono la soccombenza (<ref-law>). Non si assegnano ripetibili (<ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. Le spese giudiziarie di fr. 3'000.-- sono poste a carico del ricorrente.
3. Comunicazione al patrocinatore del ricorrente, alla Camera per l'avvocatura e il notariato del Tribunale d'appello e alla Commissione di ricorso sulla magistratura del Cantone Ticino.