Fatti:
A. A partire dal 17 febbraio 2004 A.A._ e B.A._ hanno prestato servizio presso l'Hotel C._: il primo con la funzione di "gerente" e la seconda di "aiuto gerente".
Con scritto del 18 giugno 2004 entrambi hanno rescisso il contratto per il 30 giugno 2004, continuando tuttavia a lavorare presso l'albergo durante il mese di luglio e parte del mese di agosto.
Cessata l'attività, sono sorti dei disaccordi in merito alle richieste di liquidazione formulate da A.A._ e B.A._ in relazione a giorni di riposo, di festa e di vacanza non goduti nonché a ore di lavoro supplementari.
B. Preso atto del rifiuto opposto da C._AG a tali richieste, l'8 novembre 2005 A.A._ e B.A._ l'hanno convenuta - con due atti separati - dinanzi alla Pretura del Distretto di Leventina.
B.a A.A._ ha domandato il pagamento di fr. 25'908.60 lordi (fr. 23'646.50 netti) oltre a interessi al 5 % dal 1° agosto 2004, così composti: fr. 2'379.-- per 15.86 giorni di vacanza; fr. 552.30 per 2.7 giorni di festa; fr. 7'977.30 per 39 giorni di riposo; fr. 15'000.-- per ore supplementari (700.5 ore che di per sé gli avrebbero dato diritto a fr. 21'650.05). Successivamente ha aumentato la propria pretesa a fr. 28'154.70 lordi, portando a fr. 736.40 la somma per (3.6) giorni festivi e aggiungendo fr. 2'062.-- lordi a valere quale quota parte della tredicesima mensilità (inc. DI.2005.55).
B.A._ ha domandato il pagamento di fr. 16'625.-- lordi (fr. 15'153.50 netti) oltre a interessi al 5 % dal 1° agosto 2004, così composti: fr. 1'850.35.-- per 15.86 giorni di vacanza; fr. 429.55 per 2.7 giorni di festa; fr. 5'727.30 per 36 giorni di riposo; fr. 8'617.80 per 358.5 ore supplementari. Successivamente ha aumentato la propria pretesa a fr. 18'372.45 lordi, portando a fr. 573.-- la somma per (3.6) giorni festivi e aggiungendo fr. 1'604.-- lordi a valere quale quota parte della tredicesima mensilità (inc. DI.2005.56).
B.b Congiunte le cause per istruttoria, il 28 luglio 2008 il Pretore ha emanato due sentenze motivate in maniera sostanzialmente identica, riconoscendo a A.A._ fr. 25'908.50 lordi, oltre interessi al 5 % dal 1° agosto 2004, e a B.A._ fr. 15'016.50 lordi, oltre interessi al 5 % dal 1° agosto 2004.
In breve, sulla scorta delle risultanze istruttorie il giudice di primo grado ha stabilito che i coniugi si occupavano insieme della gestione corrente e minuta dell'esercizio pubblico, senza tuttavia disporre di una concreta indipendenza economica o organizzativa, ciò che l'ha indotto a escludere la sussistenza del contratto di gerenza indipendente asseverato da C._AG e ad ammettere invece l'esistenza di un regolare contratto di lavoro, assoggettato al Contratto collettivo nazionale di lavoro dell'industria alberghiera e della ristorazione del 1998 (CCNL 98), non avendo i coniugi A._ una funzione dirigenziale. In applicazione di questa normativa il giudice ha ammesso le loro pretese, eccezion fatta per la quota parte della tredicesima.
C. Adita da C._AG, il 26 giugno 2009 la II Camera civile del Tribunale d'appello del Cantone Ticino - con due separate sentenze dal contenuto identico - ha riformato le pronunzie pretorili nel senso dell'integrale reiezione delle richieste avanzate da A.A._ e B.A._.
Confermata l'applicabilità del CCNL 98 al rapporto di lavoro instauratosi fra le parti, la Corte cantonale ha evidenziato che in concreto non è emerso dagli atti un carico di lavoro eccessivo o un'insufficienza di personale né tantomeno è risultato che i coniugi A._ abbiano mai segnalato situazioni che impedivano loro di ripartirsi adeguatamente il lavoro, imponevano l'esecuzione di lavoro straordinario e la rinuncia a giorni di libero. Alla luce di queste circostanze, considerato anche che la mole di lavoro a carico dei coniugi A._ era in precedenza sopportata da una persona sola e che, se del caso, essi avrebbero anche potuto assumere nuovo personale, la Corte cantonale ha negato che vi fosse la necessità di svolgere ore di lavoro straordinario, senza nessuna possibilità di compensazione con tempo libero. Visto che l'importo richiesto in causa equivale quasi al loro stipendio - hanno da ultimo osservato i giudici dell'alta Corte ticinese - i ricorrenti avrebbero inoltre dovuto avvisare immediatamente C._AG del massiccio aumento del tempo di lavoro e dei relativi costi, onde permetterle di verificare e adottare, eventualmente, adeguati provvedimenti.
D. Prevalendosi della violazione del diritto di essere sentito (<ref-law>) nella forma del diritto a una decisione motivata, del divieto dell'arbitrio (<ref-law>) e delle regole sull'onere della prova (<ref-law>), sia A.A._ (inc. 4A_439/2009) sia B.A._ (inc. 4A_441/2009) sono insorti dinanzi al Tribunale federale l'11 settembre 2009, con uno scritto intitolato "ricorso in materia civile e costituzionale" volto a ottenere, previa concessione dell'effetto sospensivo al gravame, la modifica della predetta sentenza nel senso dell'accoglimento (recte: reiezione) dell'appello e della conferma della pronunzia pretorile, senza tuttavia alcuna riduzione delle ripetibili; in via subordinata hanno postulato il rinvio della causa all'autorità cantonale per nuovo giudizio.
La domanda di conferimento dell'effetto sospensivo è stata accolta il 7 ottobre 2009.
Con risposta del 28 dicembre 2009 C._AG, ribadita la tesi dell'avvenuta stipulazione di un contratto di gerenza indipendente, ha proposto di respingere integralmente i due gravami.

Diritto:
1. Considerato che i ricorrenti sono coniugati e patrocinati dallo stesso legale, il quale ha inoltrato al Tribunale federale due allegati motivati in maniera identica contro due sentenze anch'esse pressoché interamente identiche nel tenore, emanate nel quadro di due cause che traggono origine dalla medesima fattispecie e che vedono opposti i ricorrenti alla medesima controparte, nulla osta - in particolare dal profilo della confidenzialità - a che i due ricorsi vengano trattati insieme e decisi con un unico giudizio.
2. Il Tribunale federale si pronuncia d'ufficio e con pieno potere d'esame sulla propria competenza e sull'ammissibilità del rimedio (<ref-law>; <ref-ruling> consid. 1.1 pag. 3).
2.1 Ambedue le sentenze impugnate sono state pronunciate in una causa civile di carattere pecuniario concernente una controversia in materia di diritto del lavoro il cui valore litigioso supera fr. 15'000.--. Contro di esse è pertanto proponibile il rimedio ordinario del ricorso in materia civile (art. 72 e 74 cpv. 1 lett. a LTF). Il ricorso in materia costituzionale - a dire il vero solo menzionato nel titolo dell'allegato ricorsuale - è invece d'acchito escluso (<ref-law>).
2.2 Interposti tempestivamente (<ref-law>) dalle parti soccombenti in sede cantonale (<ref-law>) contro due decisioni finali (<ref-law>) pronunciate dall'autorità ticinese di ultima istanza (<ref-law>), i ricorsi risultano ricevibili, perlomeno sotto questo profilo.
3. Giova ricordare che la presentazione di nuove conclusioni in sede federale è inammissibile (<ref-law>). Sono considerate nuove le conclusioni che non sono state sottoposte all'autorità cantonale di ultima istanza (Bernard Corboz in Commentaire de la LTF, 2008, n. 30-31 ad <ref-law>).
In concreto, i ricorrenti tendono alla conferma delle pronunzie di primo grado, eccezion fatta per l'importo delle ripetibili, che da fr. 1'500.-- (ripetibili ridotte) vogliono vedere aumentate a fr. 1'600.--. Sennonché in sede cantonale non hanno impugnato il giudizio di primo grado su questo punto. Formulata per la prima volta dinanzi al Tribunale federale questa conclusione - peraltro non motivata - risulta pertanto inammissibile.
4. Il ricorso si avvera parzialmente inammissibile anche sotto il profilo della motivazione.
Le censure sollevate dai ricorrenti, di per sé proponibili nel quadro del ricorso in materia civile - visto che vertono sull'applicazione del diritto federale (<ref-law>) che include anche i diritti costituzionali dei cittadini (<ref-ruling> consid. 3.1, 462 consid. 2.3) - non soddisfano infatti completamente le esigenze di motivazione poste da legge e giurisprudenza.
Le censure sollevate dai ricorrenti, di per sé proponibili nel quadro del ricorso in materia civile - visto che vertono sull'applicazione del diritto federale (<ref-law>) che include anche i diritti costituzionali dei cittadini (<ref-ruling> consid. 3.1, 462 consid. 2.3) - non soddisfano infatti completamente le esigenze di motivazione poste da legge e giurisprudenza.
4.1 4.1.1 Il Tribunale federale esamina d'ufficio il diritto federale (<ref-law>). Nondimeno, tenuto conto dell'onere di allegazione e motivazione posto dall'art. 42 cpv. 1 e 2 LTF, la cui mancata ottemperanza conduce all'inammissibilità del gravame (<ref-law>), il Tribunale federale esamina di regola solo le censure sollevate (<ref-ruling> consid. 1.1 pag. 104 seg.). Nell'allegato ricorsuale occorre quindi spiegare in maniera concisa perché l'atto impugnato viola il diritto federale; la motivazione deve essere riferita all'oggetto del litigio, in modo che si capisca perché e su quali punti la decisione contestata è impugnata (<ref-ruling> consid. 2.1). Ciò significa che la parte ricorrente non può limitarsi a riproporre gli argomenti giuridici già esposti dinanzi alle autorità cantonali, bensì deve confrontarsi criticamente con i considerandi della decisione impugnata che reputa lesivi del diritto (<ref-ruling> consid. 2a pag. 400; sentenza 4A_22/2008 del 10 aprile 2008 consid. 1).
4.1.2 Le esigenze di motivazione sono più rigorose quando viene fatta valere la violazione di diritti fondamentali, inclusa la violazione del divieto dell'arbitrio nell'applicazione del diritto cantonale rispettivamente nella valutazione delle prove e dell'accertamento dei fatti. Il Tribunale federale tratta infatti queste censure solo se la parte ricorrente le ha sollevate e motivate (<ref-law>): nell'atto di ricorso è in particolare necessario menzionare i fatti essenziali ed esporre in modo conciso le ragioni per le quali si ritiene che la decisione impugnata abbia leso dei diritti fondamentali, indicando precisamente quali. Solo le censure sollevate in maniera chiara e dettagliata vengono esaminate; censure di carattere appellatorio sono inammissibili. In particolare, il ricorrente che lamenta una violazione del divieto d'arbitrio (<ref-law>) non può limitarsi a criticare la decisione impugnata come in una procedura d'appello, dove l'autorità di ricorso gode di cognizione libera, opponendo semplicemente la propria opinione a quella dell'autorità cantonale, bensì deve confrontarsi criticamente con la sussunzione contestata e indicare in maniera chiara e dettagliata per quale motivo essa è manifestamente insostenibile (<ref-ruling> consid. 2.2 pag. 246).
4.1.3 I ricorrenti disattendono queste regole laddove rimproverano al Tribunale d'appello di essere caduto in "palese arbitrio nell'applicazione delle norme cantonali di procedura che vietano la presa in considerazione di nova in appello", ma non indicano quali sarebbero le norme cantonali violate né per quale motivo sarebbero state violate.
Per lo stesso motivo dev'essere dichiarato inammissibile anche l'argomento relativo al mancato riconoscimento di alcuni giorni di vacanza non goduti, che la controparte medesima aveva concesso in sede di risposta di causa. A prescindere dal fatto che l'opponente, con la risposta al gravame, contesta recisamente la portata attribuita dai ricorrenti alle sue dichiarazioni, nell'allegato ricorsuale non viene specificato quali sarebbero le norme del diritto processuale arbitrariamente violate dalla mancata considerazione di circostanze ammesse da una parte.
4.2 Per quanto riguarda l'accertamento dei fatti, in linea di principio il Tribunale federale fonda il proprio ragionamento giuridico sui fatti così come accertati dall'autorità inferiore (<ref-law>); nuovi fatti e nuovi mezzi di prova possono essere addotti soltanto se ne dà motivo la decisione dell'autorità inferiore (<ref-law>). Il Tribunale federale può scostarsi dall'accertamento dei fatti contenuto nella sentenza impugnata o completarlo solo se è stato violato il diritto ai sensi dell'<ref-law> o se i fatti sono stati accertati in modo manifestamente inesatto (<ref-law>). Spetta alla parte che intende prevalersi di una fattispecie diversa da quella constatata nella sentenza criticata esporre in maniera circostanziata il motivo che la induce a ritenere adempiute queste condizioni; occorre inoltre che l'eliminazione dell'asserito vizio possa influire in maniera determinante sull'esito della causa (<ref-law>).
4.2.1 Dato che la definizione di "manifestamente inesatto" corrisponde a quella di arbitrario (<ref-ruling> consid. 4.3 pag. 62), un accertamento dei fatti manifestamente inesatto configura a sua volta una violazione di un diritto fondamentale (<ref-law>; <ref-ruling> consid. 1.4.1 pag. 39) e la relativa censura deve dunque essere motivata conformemente alle esigenze poste dall'<ref-law>. Chi solleva questa censura non può pertanto limitarsi a contrapporre la propria versione dei fatti a quella contenuta nella sentenza impugnata, bensì deve allegare (e dimostrare) che il giudice del merito ha manifestamente misconosciuto il senso e la portata di un mezzo di prova, ha omesso senza valida ragione di tener conto di un elemento di prova importante, suscettibile di modificare l'esito della vertenza, oppure ha ammesso rispettivamente negato un fatto ponendosi in aperto contrasto con gli atti di causa o interpretandoli in modo insostenibile (<ref-ruling> consid. 4.3 pag. 62; <ref-ruling> consid. 2.1).
4.2.2 In ingresso al loro gravame i ricorrenti censurano siccome arbitrario l'accertamento secondo il quale essi avrebbero dovuto e potuto gestire da sé il tempo di lavoro.
Tale accertamento si basa innanzitutto sull'assenza di contestazioni da parte dei ricorrenti a questo riguardo; tale mansione era peraltro esplicitamente prevista nel contratto loro consegnato dall'opponente, ch'essi, nonostante non l'abbiano firmato, hanno parzialmente seguito, senza in particolare sollevare obiezioni circa l'obbligo di organizzare - in collaborazione fra loro - l'orario di lavoro, i giorni di riposo e i festivi. I giudici hanno inoltre rilevato che i ricorrenti avevano la possibilità di ovviare a un eccessivo carico di lavoro con l'assunzione di personale supplementare. Da ultimo, è stato constatato che non sono state addotte e dimostrate circostanze per le quali non sarebbe stato possibile ripartire adeguatamente il lavoro tra gerente e aiuto gerente, in particolare per poter usufruire di giorni di libero.
A queste considerazioni, per sostanziare "l'impossibilità materiale di gestire da sé il tempo di lavoro" vista la necessità di tenere aperto l'esercizio pubblico, i ricorrenti si limitano a opporre la mancata firma del contratto - e quindi la mancanza di consenso sul suo contenuto - e una deposizione testimoniale, giusta la quale in un'occasione la ricorrente aveva espresso il desiderio di recarsi a Lourdes e uno dei proprietari dello stabile (il teste, appunto) le aveva risposto che non vi erano problemi, "a patto che l'albergo non venisse chiuso. La medesima osservazione vale anche per i giorni di libero". Simili argomenti appellatori non ossequiano, manifestamente, le esigenze di motivazione poste alla censura di violazione del divieto dell'arbitrio, indi per cui anche su questo punto il ricorso dev'essere dichiarato inammissibile per carente motivazione.
4.2.3 Ai fini del presente giudizio verrà pertanto tenuto in considerazione il fatto - accertato in maniera vincolante per il Tribunale federale - secondo cui ai ricorrenti competeva l'organizzazione del lavoro nell'albergo, con possibilità di ripartire fra loro i vari compiti e, se necessario, di procedere all'assunzione di nuovo personale.
5. Venendo agli argomenti formulati in maniera ammissibile, va in primo luogo esaminata l'asserita violazione del diritto di essere sentito nella forma del diritto a una decisione motivata, essendosi la Corte cantonale limitata a statuire sulla domanda relativa alle ore di lavoro straordinario, senza esaminare e giudicare separatamente le pretese avanzate in relazione ai giorni di vacanza, di riposo e di festa non goduti.
5.1 Il diritto di ottenere una decisione motivata, che deriva dal diritto di essere sentito (<ref-law>), impone all'autorità di pronunciarsi nei considerandi sulle allegazioni delle parti, riferendosi agli argomenti da esse addotti. L'autorità non deve tuttavia determinarsi su tutti gli argomenti sottopostile, bensì può occuparsi delle sole circostanze rilevanti per il giudizio. Una motivazione può essere ritenuta sufficiente quando l'autorità menziona, almeno brevemente, i motivi che l'hanno indotta a decidere in un senso piuttosto che nell'altro e pone quindi l'interessato nella condizione di rendersi conto della portata del giudizio e delle eventuali possibilità di impugnazione (<ref-ruling> consid. 4.1 pag. 88 con rinvii).
5.2 In concreto, nelle circostanze descritte al consid. 4.2.2, i giudici ticinesi hanno stabilito che i ricorrenti avrebbero senz'altro potuto disporre dei giorni di libero - rispettivamente svolgere le attività di loro competenza nel normale tempo di lavoro - se avessero organizzato l'orario di lavoro in maniera corrispondente; per questo motivo hanno assimilato il lavoro fornito dai ricorrenti durante i giorni di riposo, i giorni festivi e le vacanze a ore di lavoro straordinario.
I ricorrenti hanno perfettamente colto il senso e la portata della motivazione della sentenza impugnata. Il fatto ch'essi siano dell'avviso che le condizioni per la remunerazione del lavoro straordinario vanno distinte da quelle per la retribuzione dei giorni di vacanza, di risposo e festivi non rende incompleta o incomprensibile la motivazione del giudizio cantonale. La censura relativa alla violazione del diritto di essere sentito deve quindi essere respinta siccome infondata.
6. A mente dei ricorrenti, la decisione di respingere le pretese da loro avanzate in relazione ai giorni di vacanza, di riposo e festivi nonché alle ore di lavoro straordinario sarebbe il risultato di un apprezzamento delle prove arbitrario, vietato dall'<ref-law>
6.1 Per giurisprudenza invalsa, l'arbitrio non si realizza già qualora la soluzione proposta con il ricorso possa apparire sostenibile o addirittura migliore rispetto a quella contestata; il Tribunale federale annulla la pronunzia criticata per violazione dell'<ref-law> solo se il giudice del merito ha emanato un giudizio che appare - e ciò non solo nella sua motivazione bensì anche nell'esito - 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 della giustizia e dell'equità (<ref-ruling> consid. 1.3 pag. 4).
Nell'ambito dell'apprezzamento delle prove e dell'accertamento dei fatti il giudice del merito dispone di un ampio margine di apprezzamento. Secondo la giurisprudenza egli incorre nell'arbitrio se misconosce manifestamente il senso e la portata di un mezzo di prova, se omette senza valida ragione di tener conto di un elemento di prova importante, suscettibile di modificare l'esito della vertenza, oppure se ammette o nega un fatto ponendosi in aperto contrasto con gli atti di causa o interpretandoli in modo insostenibile (<ref-ruling> consid. 4.3 pag. 62; <ref-ruling> consid. 2.1).
6.2 I ricorrenti contestano la decisione della Corte cantonale di ritenere non dimostrata l'avvenuta esecuzione di ore di lavoro straordinario né la loro segnalazione. Tre testi hanno infatti confermato in modo univoco ch'essi erano presenti nell'albergo dalle sei del mattino alle dieci di sera; la stessa opponente ha ammesso nella risposta di causa che all'inizio del giugno 2004 i ricorrenti si erano lamentati per la complessità della gestione dell'albergo e per la difficoltà di reperire personale; infine, uno dei proprietari dell'immobile, sentito quale testimone, ha dichiarato di aver saputo che uno dei motivi di lamentela dei ricorrenti era il sovraccarico di lavoro. Da ultimo, osservano i ricorrenti, l'opponente non può seriamente pretendere di non essere stata a conoscenza della situazione, visto che la gerente si recava giornalmente in albergo.
Questi argomenti sono votati all'insuccesso. Dagli estratti delle testimonianze citati nei ricorsi non risulta infatti un'immagine univoca e le dichiarazioni riportate non fanno apparire manifestamente insostenibile il giudizio impugnato. In particolare, la presenza dei ricorrenti in albergo dal mattino presto alla sera tardi non invalida l'accertamento dei giudici ticinesi secondo cui essi avrebbero potuto compensare le ore supplementari con del tempo libero. E il fatto che poco prima di rescindere il contratto i ricorrenti avessero comunicato una situazione complessa e difficoltà nel reclutare personale non significa ancora ch'essi avessero notificato l'esecuzione di ore di lavoro straordinario; la conclusione dei giudici ticinesi, secondo cui i ricorrenti non hanno avvisato l'opponente dell'esecuzione delle ore di lavoro straordinario asseverate in causa, resiste pertanto alla censura di arbitrio.
7. A mente dei ricorrenti, i giudici cantonali avrebbero in ogni caso dovuto trattare separatamente le singole pretese da loro avanzate in relazione ai giorni di vacanza, di riposo e di festa non goduti e per le ore di lavoro straordinario. Così facendo hanno violato le regole sulla ripartizione della prova, disciplinate dall'<ref-law> e, nel caso in esame, anche dal contratto collettivo. Toccava infatti all'opponente, in applicazione del CCNL 98, registrare l'orario di lavoro effettivo e i giorni di riposo; in assenza di un simile controllo avrebbe dovuto essere riconosciuta valenza probatoria al conteggio dei ricorrenti.
7.1 L'<ref-law> regola, per tutti i rapporti giuridici retti dal diritto civile federale, la ripartizione dell'onere probatorio e, pertanto, le conseguenze dell'assenza di ogni prova (<ref-ruling> consid. 5 pag. 231 seg; <ref-ruling> consid. 3.1 pag. 323). Questa norma non disciplina per contro l'apprezzamento probatorio, ovvero non prescrive al giudice quali prove assumere né come valutare le risultanze dell'istruttoria (<ref-ruling> consid. 3c pag. 223). Quando, sulla base dell'apprezzamento delle prove, il giudice raggiunge il convincimento della veridicità del fatto allegato, la questione della ripartizione dell'onore della prova non si pone più e la censura fondata sulla violazione dell'<ref-law> diviene senza oggetto (<ref-ruling> consid. 4.3.4 pag. 241; <ref-ruling> consid. 5.4 pag. 601seg). Questi principi valgono anche qualora si debba giudicare sull'esecuzione di ore di lavoro straordinario e sulla loro compensazione con giorni di riposo, festivi e di vacanza (<ref-ruling> consid. 2b/aa pag. 277).
7.2 In concreto, come già ripetuto, sulla scorta delle risultanze istruttore la Corte cantonale ha stabilito che i ricorrenti potevano compensare con tempo libero le ore di lavoro prestate durante i giorni di riposo, festivi e di vacanza, senza dover fornire lavoro straordinario. Il Tribunale d'appello si è basato in particolare sul fatto che la precedente gerente riusciva a far fronte al carico di lavoro dell'albergo da sola - mentre i ricorrenti erano in due e non risulta vi sia stato un aumento rispetto a prima - e sulla possibilità loro concessa di ovviare a un eccessivo carico di lavoro mediante l'assunzione di personale supplementare. Questi accertamenti, unitamente a quello - non adeguatamente contestato - secondo cui i ricorrenti non avevano segnalato la necessità di svolgere lavoro straordinario né di assumere nuovo personale, fanno apparire sostenibile la valutazione probatoria dei giudici ticinesi. La conclusione per cui, in concreto, le circostanze non esigevano un tempo di lavoro superiore a quello convenuto (cfr. <ref-law>), merita di essere condivisa.
7.3 Per il resto, non si vede per quale motivo - né i gravami forniscono alcuna indicazione a questo riguardo - la Corte cantonale avrebbe violato il diritto federale omettendo di vagliare separatamente le pretese avanzate in relazione ai giorni di riposo, festivi e di vacanza.
L'art. 15 n. 1 CCNL 98 definisce l'orario di lavoro medio settimanale - massimo in 42 ore con 5 settimane di vacanze, rispettivamente in 41 ore con 4 settimane di vacanze - e al n. 5 stabilisce che gli straordinari (ovvero le ore di lavoro che superano la durata media della settimana lavorativa concordata) devono di principio essere compensati con tempo libero di pari durata entro un tempo ragionevole. Il CCNL non differenzia dunque il lavoro prestato durante i giorni di riposo, da quello prestato durante giorni festivi rispettivamente di vacanza.
7.4 Da ultimo si osserva che, in assenza di un saldo di ore di lavoro straordinario, gli argomenti relativi alla loro quantificazione cadono nel vuoto.
8. In conclusione, nella misura in cui sono ammissibili, i gravami devono venire respinti siccome infondati.
Le spese giudiziarie e le ripetibili seguono la soccombenza (art. 66 cpv. 1 e 5 LTF, art. 68 cpv. 1, 2 e 4 LTF). Conformemente a quanto prescritto dall'art. 65 cpv. 4 lett. c LTF, che su questo punto deroga all'<ref-law>, la procedura dinanzi al Tribunale federale non è gratuita, nonostante verta su una controversia in materia di contratto di lavoro con un valore litigioso inferiore a fr. 30'000.--. Dato che il valore di causa non supera fr. 30'000.-- l'importo delle spese giudiziarie è tuttavia ridotto (art. 65 cpv. 4 lett. c LTF). Questo principio non vale per le ripetibili.

Per questi motivi, il Tribunale federale pronuncia:
1. Le cause 4A_439/2009 e 4A_441/2009 sono congiunte.
2. Nella misura in cui sono ammissibili, i ricorsi sono respinti.
3. Le spese giudiziarie di fr. 800.-- sono poste a carico dei ricorrenti in solido, i quali rifonderanno all'opponente, sempre con vincolo di solidarietà, fr. 3'000.-- per ripetibili della sede federale.
4. Comunicazione ai patrocinatori delle parti e alla II Camera civile del Tribunale d'appello del Cantone Ticino.