Fatti:
A. A.a In seguito a un controllo, l'Ufficio dell'assicurazione malattia del Cantone Ticino (UAM) ha constatato agli inizi del 2008 che, malgrado ritenesse di averli informati al momento del rilascio del permesso G e anche in seguito mediante operazioni di recupero, oltre 10'000 lavoratori frontalieri italiani non avevano fatto uso della facoltà accordata loro dall'Accordo del 21 giugno 1999 tra la Comunità europea e i suoi Stati membri, da una parte, e la Confederazione Svizzera, dall'altra, sulla libera circolazione delle persone (ALC; RS 0.142.112.681) di esercitare il diritto di opzione in favore del Paese di residenza per la copertura delle cure medico-sanitarie ed essere di conseguenza esentati in Svizzera. In considerazione dell'elevato numero di persone interessate e delle difficoltà da esse incontrate nel capire l'importanza (e le modalità) del diritto di opzione, l'autorità cantonale, d'intesa con quelle federali (Ufficio federale della sanità pubblica [UFSP] e Ufficio federale delle assicurazioni sociali), ha pertanto deciso nel giugno 2008 di "regolarizzare" questi lavoratori. L'amministrazione ha così avviato una procedura in sanatoria e ha assegnato un periodo supplementare, di carattere unico e straordinario, scadente il 30 settembre 2008, per esercitare (nuovamente) il diritto di opzione. La misura è stata comunicata dal Consiglio di Stato mediante bollettino stampa del 3 giugno 2008. Inoltre, l'UAM ha pure avvisato personalmente, con comunicazione postale (non raccomandata) del 12 giugno 2008 inviata al loro recapito in Italia, i diretti interessati facendo presente che in assenza di una loro determinazione essi sarebbero stati obbligati ad assicurarsi in Svizzera e con loro ogni familiare non esercitante un'attività lavorativa. Con le medesime modalità sono infine stati informati anche i rispettivi datori di lavoro oltre a diverse organizzazioni sindacali ed altri enti.
A.b Con decisione del 10 febbraio 2009 e con effetto da tale data, l'UAM ha affiliato d'ufficio presso la Sanitas Assicurazioni SA M._, cittadino italiano residente in Italia, il quale lavora in Svizzera in qualità di manovale presso la P._ SA ed è al beneficio di un permesso G per frontalieri dal 2003. L'amministrazione ha adottato questo provvedimento dopo avere osservato che l'interessato aveva lasciato trascorrere infruttuosamente anche il termine di sanatoria del 30 settembre 2008 che gli era stato comunicato con lo scritto del 12 giugno 2008.
A.c Mediante reclamo del 27 febbraio 2009 M._ si è opposto a tale provvedimento. Facendo valere di non avere ricevuto la comunicazione del 12 giugno 2008 e di non essere stato informato nemmeno in altro modo, l'interessato, peraltro già coperto in Italia per le cure sanitarie, ha dichiarato di volere esercitare il diritto d'opzione in favore del sistema sanitario del suo Paese di residenza. Da parte sua, con provvedimento del 14 maggio 2009 l'UAM ha respinto il reclamo.
B. M._ è insorto al Tribunale delle assicurazioni del Cantone Ticino, il quale, compiuti alcuni accertamenti, ha confermato l'operato dell'amministrazione e respinto il ricorso dell'interessato (pronuncia del 10 novembre 2009). La Corte cantonale ha in sostanza dato atto all'UAM di avere adempiuto al proprio obbligo di informazione e ha ritenuto tardiva l'opzione formulata il 27 febbraio 2009.
C. M._ si è aggravato al Tribunale federale al quale, in sintesi, chiede di annullare il giudizio impugnato e di attestargli l'avvenuto e regolare esercizio del diritto di opzione in favore del sistema sanitario italiano. In particolare ribadisce di non avere avuto notizia, prima della decisione di affiliazione d'ufficio del 10 febbraio 2009, della sanatoria messa in atto dalle autorità svizzere, né attraverso la comunicazione non raccomandata del 12 giugno 2008, mai pervenutagli, né per mezzo di un'informazione del suo datore di lavoro e neppure in altro modo.
D. In considerazione della moltitudine di ricorsi (oltre una ventina) inoltrati a questa Corte sullo stesso tema, con decreto del 19 gennaio 2010 il giudice dell'istruzione ha sospeso la procedura in attesa di evadere un caso pilota (causa 9C_1042/2009). Resa il 7 settembre 2010 la sentenza nella causa pilota, il giudice dell'istruzione ha riattivato la procedura per decreto del 22 settembre seguente.
Invitati ad esprimersi, l'UAM (ormai parzialmente integrato, per gli aspetti qui di interesse, nell'Ufficio dei contributi dell'Istituto cantonale delle assicurazioni sociali) ha aderito alle conclusioni ricorsuali, mentre l'UFSP ha rinunciato a determinarsi.
Diritto:
1. Il Tribunale federale ha risolto nella sentenza citata DTF 9C_1042/2009 del 7 settembre 2010 le questioni che sono ugualmente sollevate con il presente ricorso.
In quella occasione, questa Corte ha ricordato come in virtù del diritto di opzione previsto convenzionalmente, le persone residenti in Italia e che lavorano in Svizzera possono scegliere se assicurarsi - insieme ai familiari senza attività lucrativa - in Svizzera secondo il regime di assicurazione malattia della LAMal oppure in Italia secondo il sistema sanitario nazionale italiano, fermo restando però che l'eventuale esenzione dall'obbligo di assicurazione in Svizzera deve essere chiesta con una domanda che va presentata alla competente autorità cantonale in materia di assicurazione malattia del luogo di lavoro entro i tre mesi successivi all'obbligo di assicurarsi in Svizzera (Allegato II, Sezione A cpv. 1 lett. o cifra 3 b aa e bb; sentenza citata DTF 9C_1042/2009 consid. 2.3.3). Pur dando atto che questo termine di tre mesi non era stato rispettato, detta Corte ha osservato che il diritto di opzione era comunque stato ristabilito dalla successiva messa in atto della procedura in sanatoria del giugno 2008 (sentenza citata DTF 9C_1042/2009 consid. 2.3.4). Questa sanatoria era motivata con la possibilità concessa dall'Allegato II ALC (Sezione A cpv. 1 lett. o cifra 3 b aa seconda frase) di rendere efficace l'esenzione dall'inizio dell'assoggettamento all'assicurazione obbligatoria quando in casi giustificati la richiesta è presentata dopo il termine di tre mesi. Essa era inoltre giustificata dalle difficoltà incontrate dai lavoratori frontalieri italiani nel comprendere ed esercitare il diritto di opzione come pure dall'enorme mole di lavoro e dai rischi di incasso che l'affiliazione d'ufficio di così tante persone avrebbe comportato per il Cantone Ticino e gli assicuratori (sentenza citata, consid. 3.1). Ritenuto come l'operazione avesse permesso di "regolarizzare" il 95.8 % dei frontalieri interessati che hanno optato per la copertura sanitaria nel proprio Paese di residenza, rimaneva da verificare la situazione di diversi lavoratori che lamentavano di non avere ricevuto alcuna comunicazione (personale, tramite il datore di lavoro o in altro modo) prima della loro affiliazione d'ufficio alla LAMal (sentenza citata, consid. 3.1 in fine). Alla misura in sanatoria è quindi stato riconosciuto effetto costitutivo poiché modificando la situazione giuridica esistente e ristabilendo la facoltà di opzione convenzionalmente scaduta, essa aveva istituito un nuovo diritto, seppur vincolato al rispetto di un termine ben preciso. In questo modo la Corte federale ha escluso che la sanatoria potesse essere ridotta a una semplice comunicazione di natura meramente informativa priva di conseguenze giuridiche (sentenza citata, consid. 5.6). Scartata l'ipotesi della semplice informazione (che aveva per contro sostenuto il Tribunale cantonale), l'esatta natura del provvedimento poteva a questo punto rimanere indecisa perché in ogni caso - sia che si considerasse la comunicazione del 12 giugno 2008 come una decisione individuale-concreta o diffida o come altro documento ai sensi dell'art. 3 n. 3 del regolamento n. 574/72, sia si volesse qualificare la sanatoria in quanto tale quale atto generale-astratto o generale-concreto -, la sostanza non mutava. Infatti, dal momento che la corretta notifica (o pubblicazione su un organo ufficiale) non era avvenuta o non aveva potuto essere dimostrata, l'atto non poteva esplicare effetti giuridici negativi (sentenza citata, consid. 5.8). Di conseguenza ci si poteva e doveva basare sulla dichiarazione dell'insorgente che sosteneva di essere venuto a conoscenza della possibilità di sanatoria soltanto con la decisione di affiliazione d'ufficio (sentenza citata, consid. 5.9). Insorgente che avendo prontamente reagito poteva dunque validamente chiedere di essere esentato dall'obbligo assicurativo in Svizzera con effetto ex tunc, vale a dire dall'inizio del suo ipotetico assoggettamento, anche perché con l'esibizione della copia della tessera europea di assicurazione malattia rilasciata dalla Regione Lombardia aveva dimostrato di essere coperto in caso di malattia sia nello Stato di residenza sia durante un soggiorno in un altro Stato membro della Comunità europea o in Svizzera (art. 2 cpv. 6 OAMal; sentenza citata, consid. 5.10 e 6.1).
2. Considerata la similitudine della fattispecie sottoposta a giudizio nella presente vertenza con quella esaminata nella sentenza pilota e in mancanza della prova della notifica (o comunque della pubblicazione su un organo ufficiale) dell'atto con cui era stata concessa la possibilità di chiedere, in via di sanatoria, l'esenzione dall'obbligo assicurativo in Svizzera e di optare in favore del sistema sanitario italiano, ci si poteva e doveva basare sulla dichiarazione dell'insorgente che ha sempre sostenuto di essere venuto a conoscenza della possibilità di sanatoria soltanto con la decisione di affiliazione d'ufficio del 10 febbraio 2009. Avendo per il resto prontamente reagito ed esibito copia della tessera europea di assicurazione malattia rilasciata dalla Regione Lombardia, M._ poteva dunque validamente esercitare il diritto di opzione in favore del sistema sanitario italiano in sede di reclamo contro la decisione di assoggettamento d'ufficio alla LAMal.
3. 3.1 Ne segue che il ricorso si dimostra fondato e che il giudizio impugnato come pure la decisione su reclamo dell'UAM devono essere annullati. In loro riforma (art. 107 cpv. 2 LTF), al ricorrente va riconosciuta l'esenzione in Svizzera dall'assicurazione malattia obbligatoria.
3.2 Le spese giudiziarie seguono la soccombenza (art. 66 cpv. 1 LTF) e andrebbero di principio poste a carico del Cantone Ticino poiché l'UAM (e in seguito l'Ufficio dei contributi) ha operato in qualità di organo cantonale di controllo dell'assicurazione malattia ai sensi dell'art. 6 LAMal (cfr. SVR 2010 KV n. 10 pag. 43 [9C_182/2009] consid. 8 con riferimento). Al Cantone, che ha agito nell'esercizio delle sue attribuzioni ufficiali, non possono però essere caricate spese giudiziarie (art. 66 cpv. 4 LTF). Esso dovrà nondimeno rifondere al ricorrente, patrocinato da un'organizzazione sindacale, un'indennità - ridotta vista la motivazione standard utilizzata dal medesimo patrocinatore anche in altri casi (sentenza inedita del Tribunale federale delle assicurazioni U 3/98 del 25 febbraio 1998 consid. 4) - per ripetibili della sede federale (art. 68 cpv. 2 LTF). La domanda di assistenza giudiziaria del ricorrente è priva di oggetto.
Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso è accolto. Il giudizio del Tribunale delle assicurazioni del Cantone Ticino del 10 novembre 2009 e la decisione su reclamo dell'Ufficio cantonale dell'assicurazione malattia del 14 maggio 2009 sono annullati. Il ricorrente è esentato dall'obbligo di assicurazione malattia in Svizzera.
2. Non si prelevano spese giudiziarie.
3. L'opponente verserà al ricorrente la somma di fr. 800.- a titolo di indennità di parte per la procedura federale.
4. Il Tribunale delle assicurazioni del Cantone Ticino statuirà sulla questione delle spese ripetibili di prima istanza, tenuto conto dell'esito del processo in sede federale.
5. Comunicazione alle parti, al Tribunale delle assicurazioni del Cantone Ticino e all'Ufficio federale della sanità pubblica.