Fatti:
A. Il 9 settembre 2008 il Consiglio di Stato del Cantone Ticino ha adottato una revisione del regolamento dell'11 novembre 2003 che disciplina le notifiche degli ospiti alla polizia (RL/TI 11.3.2.3; BU 2003 326; BU 2008 524; di seguito: il Regolamento). La revisione consisteva nell'introduzione di una norma supplementare sulla notifica via internet e nella modifica di cinque dei dieci articoli di cui si componeva il Regolamento, essenzialmente per tener conto di questa novità. Pubblicata nel Bollettino ufficiale delle leggi e degli atti esecutivi del 12 settembre 2008, la novella legislativa prevedeva tra l'altro le disposizioni seguenti:
Art. 1 [Titolo marginale: A. Principio I. In generale]
Il datore di alloggio notifica alla polizia cantonale l'arrivo di ogni ospite:
a) che intende pernottare in campeggio, in esercizio pubblico con alloggio o in azienda agricola agrituristica;
b) che intende pernottare a pagamento in un altro posto di alloggio o che pernotta gratuitamente per una durata superiore ai 30 giorni.
Art. 1a (nuovo) [Titolo marginale: II. Mediante il programma informatico]
1Le notifiche sono trasmesse alla polizia cantonale mediante un programma accessibile via internet.
2Sono esonerati dall'utilizzo di tale programma:
a) le strutture con meno di 5 posti letto;
b) le strutture che, per motivi tecnici, ad esempio, perché non sono allacciate alla corrente, o perché sono prive di una connessione internet, non possono accedervi.
Art. 2
1Le famiglie (marito, moglie, figli) sono notificate con un unico bollettino o inserendo una sola volta i dati del capo famiglia, indipendentemente dall'età dei figli, indicando il numero dei congiunti e il numero di questi ultimi con più e rispettivamente meno di 14 anni.
2Tutti gli altri parenti o accompagnatori devono essere notificati separatamente.
Art. 8
Il datore di alloggio è responsabile della trasmissione di dati completi, esatti e leggibili.
II. La presente modifica di regolamento è pubblicata nel Bollettino ufficiale delle leggi e degli atti esecutivi ed entra in vigore immediatamente.
B. Il 13 ottobre 2008 E._, F._, e G._, gerenti di esercizi pubblici ticinesi rientranti nella categoria degli affittacamere, nonché le società A._SA, B._SA, C._SA e D._Sagl, gestrici di analoghi locali, hanno interposto un ricorso in materia di diritto pubblico dinanzi al Tribunale federale con cui chiedono di annullare gli art. 1, 1a, 2, 8 e II del suddetto regolamento. Dei motivi si dirà, per quanto necessario, nel seguito.
Chiamato ad esprimersi, il Consiglio di Stato ha postulato che il ricorso sia respinto. Nell'ambito di un secondo scambio di allegati, i ricorrenti hanno ribadito le richieste di giudizio esposte nel gravame mentre il Governo cantonale non ha presentato osservazioni.
C. Con decreto presidenziale del 30 ottobre 2008 è stata accolta la domanda di concessione dell'effetto sospensivo formulata nel ricorso.

Diritto:
1. 1.1 L'impugnativa è diretta contro un atto normativo cantonale ed è stata interposta entro trenta giorni dalla pubblicazione delle modifiche legislative nel relativo organo ufficiale. Inoltre il diritto ticinese non prevede alcuna procedura di controllo astratto delle norme (<ref-ruling> consid. 1b; sentenza 2C_165/2007 del 19 febbraio 2008 consid. 2.1, in RtiD II-2008 n. 36). Il gravame è quindi di massima ammissibile sotto il profilo degli art. 82 lett. b, 87 cpv. 1 e 101 LTF.
In quanto titolari o responsabili di esercizi pubblici dediti all'affitto di camere o di altre unità abitative per soggiorni di breve durata (cfr. art. 5 lett. n della legge ticinese del 21 dicembre 1994 sugli esercizi pubblici [LEsPubb]; RL/TI 11.3.2.1]), i ricorrenti, o in ogni caso coloro tra essi che appartengono ad una delle due figure professionali in cui si suddividono, sono particolarmente toccati dalla regolamentazione impugnata in maniera effettiva o quantomeno virtuale ed hanno un interesse degno di protezione al suo annullamento. In virtù dell'<ref-law>, costoro sono pertanto legittimati a ricorrere (cfr. <ref-ruling> consid. 1.4; <ref-ruling> consid. 2.2).
1.2 Come già accennato, la contestata revisione legislativa contiene un'unica vera novità, l'art. 1a del Regolamento, mentre per il resto, con un'eccezione all'art. 1 lett. b, apporta adeguamenti essenzialmente formali, in funzione della nuova modalità di trasmissione dei dati via internet. Più in particolare, all'art. 1 sono state abbandonate la locuzione "mediante compilazione di un apposito bollettino" all'inizio e la limitazione allo "straniero" alla lett. b, all'art. 2 è stato aggiunto il passaggio "o inserendo una sola volta i dati del capo famiglia" e all'art. 8 il termine "bollettini" è stato sostituito con "dati". La portata del tutto secondaria di queste modifiche non influisce comunque sull'ammissibilità del gravame. La giurisprudenza ammette infatti che se la revisione di una norma non ne muta il contenuto essenziale bensì solo elementi secondari, anche gli aspetti ripresi dall'ordinamento precedente possono venir sottoposti ad un nuovo controllo (<ref-ruling> consid. 1; sentenza 2P.440/1995 del 12 marzo 1997 consid. 1e, in RDAT 1997 II n. 33; sentenza 2C_77/2007 del 2 aprile 2009 consid. 1; cfr. anche <ref-ruling> consid. 3.1.1; <ref-ruling> consid. 1b/aa).
1.3 Nell'allegato ricorsuale occorre spiegare in modo conciso perché l'atto impugnato viola il diritto (art. 42 cpv. 1 e 2 LTF). Esigenze più severe si applicano poi in relazione alla violazione di diritti fondamentali e di disposizioni di diritto cantonale e intercantonale. In effetti il Tribunale federale non esamina il rispetto di tali diritti d'ufficio, come per le norme legislative federali (<ref-law>), ma soltanto se i ricorrenti hanno sollevato e motivato le relative contestazioni (<ref-law>). Gli insorgenti devono quindi indicare i diritti costituzionali di cui ravvisano la violazione ed esporre in modo chiaro e circostanziato in cosa consiste la lesione (<ref-ruling> consid. 2.2; <ref-ruling> consid. 3.2). Queste esigenze valgono anche nell'ambito del controllo astratto delle norme (<ref-ruling> consid. 5.2; <ref-ruling> consid. 1.5). Nel caso di specie, la memoria di ricorso ravvisa la violazione di alcune norme legislative federali e menziona i diritti e i principi costituzionali della legalità, della separazione dei poteri e della parità di trattamento. Per larghi tratti la motivazione appare tuttavia eccessivamente generica e di natura puramente appellatoria. In questa misura l'impugnativa risulta pertanto inammissibile.
2. Nell'ambito del controllo astratto delle norme, il Tribunale federale annulla l'atto cantonale impugnato soltanto se a questo, in base alle regole d'interpretazione usuali, non può essere attribuito alcun significato che lo lasci apparire compatibile con le garanzie costituzionali o le norme di diritto federale invocate. Il Tribunale federale prescinde quindi dall'annullamento quando una simile interpretazione conforme alla costituzione o al diritto federale superiore può essere ammessa in maniera perlomeno sostenibile. Se una disposizione di portata generale ed astratta appare accettabile dal profilo costituzionale e legale in situazioni che il legislatore doveva normalmente prevedere, l'eventualità che in casi particolari essa possa invece risultare inammissibile non giustifica ancora, in generale, un intervento giudiziario allo stadio del controllo astratto delle norme. Gli interessati conservano in ogni caso la possibilità di far valere l'eventuale incostituzionalità o illegalità nel contesto di casi d'applicazione concreta (<ref-ruling> consid. 2; <ref-ruling> consid. 2; <ref-ruling> consid. 2.1).
3. 3.1 In riferimento all'art. 1 del Regolamento, i ricorrenti lamentano innanzitutto la violazione dell'art. 16 LStr (RS 142.20) e dell'art. 18 dell'ordinanza del 24 ottobre 2007 sull'ammissione, il soggiorno e l'attività lucrativa (OASA; RS 142.201). Rilevano infatti che tali disposizioni impongono di notificare soltanto gli stranieri a cui è dato alloggio a pagamento e quindi non anche coloro che pernottano gratuitamente per una durata superiore a 30 giorni, come invece previsto dall'art. 1 lett. b del Regolamento. Sostengono inoltre che non gioverebbe richiamarsi ad una normativa cantonale più severa. L'art. 53 cpv. 3 LEsPubb rende infatti responsabili delle notifiche i gerenti degli esercizi pubblici, quando invece datori di alloggio ai sensi del Regolamento sarebbero i gestori. L'obbligo di notifica sancito da tale normativa sarebbe perciò sprovvisto di una chiara base legale, con conseguente violazione dei principi della legalità e della separazione dei poteri.
3.2 La prima critica è manifestamente infondata. L'art. 1 del Regolamento non contraddice infatti il dovere di notifica sancito dall'art. 16 LStr e dall'<ref-law>, ma semplicemente lo istituisce in maniera più generalizzata, in quanto non lo limita ai cittadini stranieri ed ai soggiorni a pagamento, bensì lo estende anche agli ospiti di nazionalità svizzera ed ai pernottamenti a titolo gratuito di più di 30 giorni. La normativa cantonale si applica pertanto ad una serie più ampia di situazioni, in cui sono comunque comprese anche quelle a cui si riferisce la legislazione federale. Del resto, i ricorrenti avrebbero semmai dovuto censurare la violazione del principio della preminenza del diritto federale enunciato all'<ref-law>, adducendo che il diritto federale regola in maniera esaustiva l'obbligo di notifica di ospiti stranieri o che l'imposizione di tale obbligo anche per determinati soggiorni gratuiti viola il senso e lo spirito del medesimo ordinamento (cfr. <ref-ruling> consid. 2.1, 269 consid. 6.2; <ref-ruling> consid. 3.1). La norma contestata risulterebbe ad ogni modo ammissibile anche sotto questo profilo. In effetti il regime che essa instaura è forse più severo rispetto alla legislazione federale in materia di persone straniere, ma persegue finalità diverse e senz'altro legittime, non volte a disciplinare la situazione specifica degli stranieri, bensì fondate sulle competenze generali ed originarie dei cantoni in materia di polizia, segnatamente di polizia del commercio (cfr. RAINER J. SCHWEIZER, in Die Schweizerische Bundesverfassung, vol. 1, 2a ed., 2008, n. 6 ad <ref-law>).
3.3 Quanto alla seconda censura, l'art. 53 cpv. 3 LEsPubb stabilisce che il gerente di un esercizio pubblico con alloggio è responsabile delle notifiche degli ospiti alla polizia. Questa disposizione fissa quindi essa stessa il principio secondo cui le persone che pernottano in un esercizio pubblico vanno notificate alla polizia. La norma non limita peraltro tale obbligo ai soggiorni a pagamento. Di conseguenza, l'art. 1 del Regolamento non impone nuovi oneri ai titolari di esercizi pubblici, ma semmai, se l'eccezione per soggiorni gratuiti di breve durata (art. 1 lett. b) si applica anche a tali luoghi di alloggio, alleggerisce le loro incombenze per rapporto alla regola generale sancita dalla legge.
Il disposto litigioso può inoltre essere interpretato ritenendo che il dovere di notifica sia posto a carico dei gerenti, come indicato all'art. 53 cpv. 3 LEsPubb. La norma utilizza infatti il concetto generico di datore di alloggio perché il suo campo d'applicazione non è limitato agli esercizi pubblici, ma concerne ad esempio anche privati che danno ospitalità a terzi a titolo oneroso in maniera occasionale. D'altra parte, la pretesa ambiguità ravvisata dai ricorrenti va ricondotta al fatto che la distinzione tra la figura del gerente, cioè la persona fisica titolare del certificato di capacità (art. 3 LEsPubb), e quella del gestore, ovvero la persona o la società che ha la responsabilità economica della conduzione dell'esercizio pubblico (art. 75 del regolamento del 3 dicembre 1996 della LEsPubb [REsPubb; RL/TI 11.3.2.1.1]), non era espressamente prevista in origine dalla legge, ma è stata esplicitata solo in un secondo tempo e soprattutto a livello del regolamento, dopo una pronuncia del Tribunale federale (sentenza 2P.50/1995 del 7 marzo 1996 consid. 4, in RDAT 1996 II n. 55; MARCO GARBANI, Commentario alla LEP, 2005, pag. 116 segg.; lo stesso, La legge sugli esercizi pubblici ed alcuni termini sui generis, in RtiD 2006 I pag. 325 segg., in part. pag. 346). Ora, considerate queste due diverse figure professionali, può anche essere ammesso che, come sostenuto dagli insorgenti, il datore di alloggio vada identificato prioritariamente nel gestore, il quale dovrebbe fungere da controparte nel contratto di pernottamento con l'ospite. Il gerente è comunque la persona responsabile verso le autorità ed il gestore del rispetto delle leggi e dei regolamenti (art. 80 REsPubb). Non è quindi infondato assumere che la nozione generica di datore di alloggio possa essere riferita anche al gerente.
La controversa disposizione del Regolamento non esula pertanto dai principi stabiliti dall'art. 53 cpv. 3 LEsPubb né riguardo alla portata dell'obbligo di notifica né in riferimento alle persone a cui tale obbligo è imposto. Essa non viola quindi i principi di legalità (<ref-law>) e della separazione dei poteri (art. 51 Cost./TI; RS 131.229; <ref-ruling> consid. 2.2, 269 consid. 3.3.2). Costituisce infatti una semplice disposizione d'esecuzione, che non modifica il contenuto dell'atto legislativo da cui deriva, ma ne riprende gli scopi e si limita a precisare la regolamentazione già definita, nei suoi fondamenti, dalla normativa legale (cfr. art. 70 lett. a Cost./TI; <ref-ruling> consid. 2.4, 269 consid. 4.2; <ref-ruling> consid. 5.1).
4. 4.1 In riferimento all'art. 1a del Regolamento, gli insorgenti sostengono che la notificazione degli ospiti mediante un programma accessibile via internet comporta costi non indifferenti per l'acquisto dell'apparecchiatura informatica, dell'abbonamento telefonico e per la messa in sicurezza dei dati registrati. Osservano inoltre che il Regolamento è silente circa le condizioni di sicurezza garantite nella scritturazione e nella trasmissione dei dati nonché riguardo alle modalità di accesso agli stessi e rilevano che senza una specifica base legale non è possibile imporre a taluni cittadini di inserire nei loro computer un programma di polizia.
4.2 Mediante queste considerazioni gli insorgenti non lamentano la violazione di norme di diritto federale di rango legislativo né soddisfano di per sé le rigorose esigenze di motivazione che devono essere adempiute riguardo a censure di natura costituzionale (cfr. consid. 1.3). Ad ogni modo, considerato che gli esercizi pubblici sono esonerati dall'utilizzo della modalità di notifica per via elettronica se sono privi di connessione internet (art. 1a cpv. 2 lett. b del Regolamento), la disposizione contestata non li obbliga assolutamente a dotarsi di un'infrastruttura informatica. Inoltre nella propria risposta il Consiglio di Stato ha illustrato i provvedimenti tecnici che consentono di tutelare la sicurezza e la confidenzialità della trasmissione e della conservazione dei dati notificati. A queste spiegazioni i ricorrenti non hanno ribattuto in maniera convincente, sollevando fondati dubbi che il sistema previsto non offra sufficienti garanzie. Legittima appare poi anche l'osservazione del Governo cantonale secondo cui sarebbe stato superfluo inserire nel Regolamento disposizioni in materia di protezione di dati personali, dal momento che le informazioni raccolte soggiacciono comunque a normative specifiche, ovvero alla legge del 9 marzo 1987 sulla protezione dei dati personali (RL/TI 1.6.1.1) e alla legge del 13 dicembre 1999 sulla protezione dei dati personali elaborati dalla polizia cantonale e dalle polizie comunali (RL/TI 1.6.1.2). Infine la notifica per via informatica non richiede l'installazione nei computer privati di programmi elaborati dalle autorità e non v'è motivo di ritenere che l'accesso al sito internet predisposto per la trasmissione delle informazioni possa compromettere la funzionalità dei sistemi informatici degli utenti. In ogni caso, l'art. 1a del Regolamento stabilisce una semplice modalità operativa, come visto peraltro nemmeno imposta in maniera rigorosa, che si limita a precisare la procedura di attuazione concreta dell'obbligo di notificazione. L'utilizzo di tale modalità di notifica non deve quindi necessariamente essere sancito già dalla legge.
5. 5.1 Riguardo all'art. 2 del Regolamento, i ricorrenti contestano la nozione di capofamiglia, giudicata lesiva del principio della parità di trattamento, e sostengono che tale disposizione limita il concetto di famiglia al nucleo composto da marito, moglie e figli, risultando così discriminatoria per le coppie che vivono in unione domestica registrata e per le famiglie monoparentali.
5.2 In realtà, la precisazione "marito, moglie e figli" può servire ad indicare, in contrapposizione con il secondo capoverso, che la notificazione collettiva è concessa soltanto in presenza di un rapporto coniugale o di discendenza diretta e non di un qualsiasi vincolo di parentela. Essa non deve quindi forzatamente significare che occorre un nucleo famigliare composto cumulativamente dal marito, dalla moglie e dai figli. Potrebbe invece bastare uno dei due legami famigliari per evitare che ciascun ospite debba essere registrato singolarmente. La disposizione non risulta pertanto penalizzante per le famiglie monoparentali. Al termine di capofamiglia, ripreso da precedenti regolamentazioni analoghe (cfr., da ultimo, l'art. 6 del decreto esecutivo del 14 febbraio 1990 sulle notifiche degli ospiti alla Polizia; BU 1990 41) e certo come sostenuto dai ricorrenti forse un po' vetusto, può inoltre essere attribuito un significato neutro, senza connotazione prettamente maschile. Il disposto legale non esclude del resto che qualora gli ospiti siano uniti in matrimonio possano essere indicati i dati della moglie. La norma non comporta quindi nemmeno una discriminazione in ragione del sesso (<ref-law>). Per contro, la mancata concessione anche alle persone che vivono in unione domestica registrata della facilitazione prevista per le coppie sposate potrebbe effettivamente apparire come una distinzione discriminatoria, in quanto legata al modo di vita (<ref-law>). L'assenza di parificazione, su questo punto, tra i due istituti giuridici non è tuttavia sancita espressamente dalla disposizione litigiosa, ma deriva piuttosto dal mancato aggiornamento di quest'ultima all'introduzione dell'unione domestica registrata. Il testo legale soffre quindi di una lacuna in senso proprio (cfr. <ref-ruling> consid. 3.5; <ref-ruling> consid. 7; <ref-ruling> consid. 4.1), che potrebbe senz'altro venir colmata nel senso preteso dai ricorrenti ed espressamente ammesso anche dal Consiglio di Stato. Nel quadro del controllo astratto delle norme una simile possibilità è sufficiente per rendere la normativa costituzionalmente sostenibile (cfr. sentenza 2P.50/1995 del 7 marzo 1996 consid. 4c, in RDAT 1996 II n. 55). Anche l'art. 2 del Regolamento resiste perciò alle critiche ricorsuali.
6. 6.1 In relazione all'art. 8, gli insorgenti rilevano che la formulazione della norma sarebbe ambigua e persino contraria all'art. 6 CEDU poiché rende responsabile della trasmissione dei dati il datore di alloggio, senza precisare se si tratti del gestore oppure del gerente. Sarebbe inoltre nuovamente lesivo del principio della separazione dei poteri imporre mediante un semplice regolamento una responsabilità incondizionata al datore di alloggio anche quando costui riporta in modo corretto i dati del documento di legittimazione presentatogli, che però risulta falso o indica generalità non più attuali.
6.2 Riguardo alla prima critica, va innanzitutto ribadito che la nozione di datore di alloggio può essere riferita non solo alla figura del gestore, ma anche a quella del gerente, ed è utilizzata perché il Regolamento non trova applicazione unicamente nel caso di esercizi pubblici (cfr. consid. 3.3). Certo, di per sé detta nozione potrebbe dunque lasciare aperte due opzioni quanto al soggetto responsabile della trasmissione dei dati per gli esercizi pubblici. La norma non risulta comunque eccessivamente generica già perché deve in ogni caso essere interpretata in funzione dell'art. 53 cpv. 3 LEsPubb, che pone la responsabilità della notifica a carico del gerente. Quanto alla seconda censura, va osservato che l'obbligo di trasmettere dati completi, esatti e leggibili costituisce solo una conseguenza logica e necessaria del dovere di notifica in quanto tale. Ciò vale perlomeno nella misura in cui, com'è il caso, la responsabilità per la correttezza delle informazioni non è espressamente istituita quale responsabilità di natura causale. Ne discende che la disposizione litigiosa non impone nuovi oneri ai gerenti, i quali non potranno peraltro essere tenuti per responsabili se, senza alcuna negligenza da parte loro, trasmetteranno dati tratti da documenti non veritieri. Nemmeno sotto questo profilo il Regolamento viola dunque i principi di legalità e della separazione dei poteri.
7. 7.1 Infine in merito al punto II del Regolamento i ricorrenti criticano l'entrata in vigore immediata del medesimo, senza alcun termine transitorio, ciò che li obbligherebbe a dotarsi immediatamente della necessaria infrastruttura e comporterebbe il blocco delle attività fino al momento in cui sarà operativo il programma per le notifiche.
7.2 In realtà, già si è detto che la modifica legislativa contestata non obbliga gli esercizi pubblici a dotarsi di mezzi informatici e di una connessione internet (cfr. art. 1a cpv. 2 lett. b del Regolamento; consid. 4.2). Essa non comporta quindi oneri supplementari di rilievo per i datori di alloggio, ma costituisce semmai una facilitazione nell'espletamento dell'obbligo di notifica. Di conseguenza, non ricorrono manifestamente gli estremi per esigere un regime transitorio. Quest'ultimo può infatti risultare necessario, in determinate circostanze, soltanto se una modifica legislativa o di regolamento, che per ragioni di interesse pubblico dovrebbe di principio entrare in vigore senza ritardo, colpisce il privato cittadino in modo rilevante. Per di più, in relazione a questo aspetto, il legislatore o l'autore della regolamentazione godono di un ampio margine di apprezzamento e la giurisprudenza dà quindi prova di riserbo nel giudicare incostituzionale l'assenza di disposizioni transitorie (DTF <ref-ruling> consid. 8.1; <ref-ruling> consid. 3b/bb; sentenza 1P.298/2005 del 4 ottobre 2005 consid. 2.4).
8. In base alle considerazioni che precedono, il ricorso, nella misura in cui è ammissibile, si avvera infondato e deve pertanto essere respinto.
Secondo soccombenza, le spese giudiziarie vanno poste a carico dei ricorrenti, con responsabilità solidale (art. 65 e 66 cpv. 1 e 5 LTF). Non si assegnano ripetibili ad autorità vincenti (<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 dei ricorrenti, in solido.
3. Comunicazione al patrocinatore dei ricorrenti e al Consiglio di Stato del Cantone Ticino.