Fatti:
A. A._ ha assunto il 1° giugno 2006 C._ quale "gerente" di un albergo ristorante a Biasca. Il 22 agosto 2007 il datore di lavoro ha disdetto i contratti di tutti i dipendenti per il 30 settembre successivo in vista della cessazione dell'attività. Dopo aver invano reclamato il pagamento dei giorni di libero non goduti e delle ore straordinarie, C._ ha chiesto con petizione 26 febbraio 2008 al Pretore della giurisdizione di Blenio di condannare A._ a pagarle fr. 21'664.40, oltre interessi. Il 17 settembre 2010 il Pretore ha accolto l'azione limitatamente a fr. 19'975.65.
B. Con sentenza 14 giugno 2011 la II Camera civile del Tribunale di appello del Cantone Ticino ha respinto, nella misura in cui era ammissibile, un appello inoltrato da A._. I Giudici cantonali hanno confermato che la necessità delle ore straordinarie prestate dall'attrice era riconoscibile dal datore di lavoro e che quest'ultimo, che ha trascurato di definire le modalità di controllo di tale attività, non può prevalersi di questa omissione per escludere la rimunerazione prevista dal contratto collettivo nazionale di lavoro dell'industria alberghiera e della ristorazione (CCNL). La Corte cantonale ha poi considerato che - in seguito a tale negligenza - il Pretore si è correttamente basato sul conteggio allestito dalla lavoratrice e ha terminato la sua sentenza, rilevando che analoghe considerazioni valgono pure per il parziale accoglimento della richiesta di indennità per giorni di libero e festivi non goduti.
C. A._ postula con ricorso in materia civile del 16 agosto 2011 la riforma della sentenza impugnata nel senso che la petizione sia respinta. Il ricorrente lamenta, in sostanza, che la Corte cantonale avrebbe acriticamente riconosciuto le ore straordinarie che la lavoratrice pretende a torto di aver dovuto effettuare senza che fossero state retribuite e delle quali ha abusivamente presentato un conteggio unicamente dopo la cessazione del rapporto di lavoro.
Con risposta 20 settembre 2011 C._ propone la reiezione del ricorso.

Diritto:
1. Proposto tempestivamente (art. 46 cpv. 1 lett. b combinato con l'<ref-law>) dalla parte soccombente in sede cantonale (<ref-law>) contro una decisione finale (<ref-law>) pronunciata dall'autorità di ultima istanza del Cantone Ticino (<ref-law>) in una causa civile in materia di diritto del lavoro il cui valore litigioso supera fr. 15'000.-- (<ref-law>), il ricorso in materia civile è in linea di principio ammissibile.
2. 2.1 Il Tribunale federale esamina d'ufficio il diritto federale (<ref-law>). Nondimeno, secondo l'art. 42 cpv. 1 e 2 LTF, l'atto ricorsuale deve contenere le conclusioni della parte ricorrente e i motivi su cui esse si fondano. Ciò significa che occorre spiegare in maniera concisa perché l'atto impugnato viola il diritto. Quando viene fatta valere la violazione di diritti fondamentali le esigenze di motivazione sono più severe: giusta l'<ref-law> il Tribunale federale esamina simili censure soltanto se il ricorrente le solleva e motiva in modo circostanziato (<ref-ruling> consid. 2.5). Per lamentare con un'ammissibile censura la violazione del divieto dell'arbitrio non è segnatamente sufficiente formulare una critica meramente appellatoria (<ref-ruling> consid. 2.8) e contestare la decisione impugnata come in una procedura d'appello, nella quale l'autorità di ricorso gode di cognizione libera, opponendo semplicemente la propria opinione a quella dell'autorità cantonale (<ref-ruling> consid. 3).
Giova inoltre ricordare che in linea di principio il Tribunale federale fonda il suo ragionamento giuridico sull'accertamento dei fatti svolto dall'autorità inferiore (<ref-law>) e può scostarsene o completarlo unicamente se è stato effettuato in violazione del diritto nel senso dell'<ref-law> o in modo manifestamente inesatto (<ref-law>). L'accertamento dei fatti contenuto nella sentenza impugnata può essere censurato alle stesse condizioni (<ref-law>). Poiché la definizione di "manifestamente inesatto" corrisponde a quella dell'arbitrio (<ref-ruling> consid. 1.2.2) e configura a sua volta la violazione di un diritto fondamentale (<ref-law>; <ref-ruling> consid. 1.4.1), valgono le accresciute esigenze di motivazione poste dall'<ref-law>.
2.2 In concreto l'impugnativa, in cui argomenti di diritto e di fatto si accavallano, disattende largamente le predette esigenze di motivazione e si rivela di difficile comprensione. Qui di seguito il Tribunale federale vaglierà unicamente le tesi ricorsuali che sono sufficientemente individuabili, atteso che le altre si appalesano di primo acchito inammissibili.
3. 3.1 Con riferimento all'accertamento dei fatti, occorre innanzi tutto rilevare che, nella sentenza impugnata, la Corte cantonale si è basata sulla constatazione pretorile secondo cui l'opponente ha prestato ore straordinarie e ha osservato che, esternando "il dubbio sulla reale comprensione di alcuni elementi di fatto da parte del Pretore", il ricorrente non aveva formulato alcuna censura conforme al diritto processuale cantonale. Essa assevera inoltre che il datore di lavoro non aveva neppure confutato il giudizio di primo grado, laddove questo indicava che egli non poteva "ragionevolmente ignorare il problema delle ore supplementari svolte dall'istante". I Giudici di appello hanno pure ritenuto che l'insorgente non aveva nemmeno validamente censurato la conclusione del Pretore attinente alla mancata pattuizione di un salario flessibile, nel senso che vi fosse un accordo di compensare le ore straordinarie con la retribuzione concordata.
Nella fattispecie il ricorrente non si confronta - e non soddisfa quindi le predette esigenze di motivazione poste dall'<ref-law> (supra, consid. 2.1) - con le considerazioni dei Giudici cantonali che dichiarano l'appello irricevibile sulle predette questioni, ma si limita a sostenere che le ore straordinarie non sarebbero state prestate, perché non erano necessarie, e che esse sarebbero state pagate, atteso che il salario mensile avrebbe pure compreso un eventuale lavoro straordinario.
3.2 La Corte cantonale ha poi pure confermato la conclusione del Pretore, secondo cui vi era una - per il datore di lavoro riconoscibile - necessità di eseguire ore straordinarie.
A tal proposito il ricorrente afferma unicamente che le ore supplementari non sarebbero state necessarie, citando una deposizione che elenca il numero di dipendenti dell'esercizio pubblico, l'opinione della persona incaricata di verificare le ore dei lavoratori sottoposti ad un controllo orario, la quale riteneva che "probabilmente" i dipendenti erano in eccesso, e una testimonianza concernente la perdita d'esercizio. Così facendo, il ricorrente si limita ad apoditticamente contrapporre la sua opinione a quella dell'autorità cantonale, citando estratti di deposizioni senza pertinenza per la questione concernente la necessità di fornire ore supplementari e non formula una censura conforme alle esigenze di motivazione dell'<ref-law>. Né configura un'ammissibile censura la laconica affermazione, priva di ulteriori spiegazioni, che dalle tavole processuali emergerebbe esattamente il contrario di quanto ritenuto dalle precedenti autorità giudiziarie.
3.3 Ne segue che il Tribunale federale pone a fondamento della sua sentenza gli accertamenti secondo cui l'opponente ha effettuato ore supplementari, la cui necessità era riconoscibile dal datore di lavoro, senza che le parti avessero convenuto un salario che le includesse.
4. 4.1 I Giudici di appello hanno indicato che il datore di lavoro non può trarre profitto dal fatto che egli si era completamente disinteressato della questione delle ore di lavoro che dovevano essere prestate dalla dipendente.
4.2 Il ricorrente ritiene errata tale considerazione e afferma che l'opponente è incorsa in un abuso di diritto, perché ha reclamato il pagamento delle ore supplementari solo dopo la conclusione del rapporto di lavoro, quando una verifica delle stesse era impossibile.
4.3 Il datore di lavoro ha un interesse a che il lavoratore gli segnali le ore straordinarie effettuate, segnatamente per permettergli di prendere i provvedimenti necessari per evitare in futuro ulteriore lavoro straordinario (<ref-ruling> consid. 2.2). L'interesse a una comunicazione immediata non è per contro ravvisabile quando il datore di lavoro deve riconoscere dalle circostanze che è necessaria la prestazione di ore supplementari nel senso dell'<ref-law> e può quindi già prendere le opportune misure; in questa situazione può inoltre essere da lui preteso, qualora desideri conoscere il numero esatto delle ore supplementari effettuate, di informarsi presso il dipendente (<ref-ruling> consid. 2.3). Il Tribunale federale ha inoltre già avuto modo di indicare che il diritto del lavoratore al pagamento delle ore straordinarie non diventa perento, se quest'ultimo ha unicamente fatto valere tale diritto 6 mesi dopo il termine del rapporto di lavoro (<ref-ruling> consid. 2.4).
Nell'impugnativa in esame il ricorrente lamenta che non gli era possibile controllare le ore lavorative effettuate - perché non gli è mai stato presentato il relativo rendiconto né un piano di lavoro - e continua ad illustrare i provvedimenti presi tramite "il responsabile del controllo delle ore" nei confronti dei dipendenti che erano soggetti alla timbratura del cartellino orario, ma nemmeno sostiene di aver mai chiesto all'opponente, che non era sottoposta a una tale verifica del tempo di lavoro, quante ore supplementari avesse svolto. In queste circostanze al ricorrente, ricordata la sua passività e la riconoscibilità del lavoro straordinario svolto, non è di soccorso alcuno il fatto che l'opponente abbia presentato il conteggio delle ore straordinarie alcuni mesi dopo la fine del rapporto di lavoro.
5. Per quanto riguarda la quantificazione del lavoro straordinario eseguito, giova ricordare che, qualora il lavoratore abbia dimostrato di aver svolto delle ore supplementari, il cui numero non può più essere stabilito in modo esatto, il giudice può stimarlo in applicazione dell'<ref-law>. L'alleggerimento dell'onere probatorio non conduce tuttavia al rovesciamento dell'onere della prova (<ref-ruling> consid. 2b/aa). Nella misura del possibile il lavoratore deve allegare e provare tutte le circostanze che permettono di valutare il numero di ore supplementari eseguite, poiché la conclusione per cui le ore supplementari sono state eseguite nella misura asserita deve imporsi al giudice con una certa forza (sentenza del 24 agosto 2006 nella causa 4C.141/2006 consid. 4.2.2, in RSPC 2007 pag. 166). Il CCNL concede un'ulteriore facilitazione probatoria a favore del lavoratore in questo ambito. Posto che l'art. 15 n. 7 CCNL impone al datore di lavoro l'obbligo di rilevare le ore di lavoro svolte dal dipendente, l'art. 21 n. 3 CCNL (nel tenore applicabile alla fattispecie) stabilisce che, se il datore di lavoro non adempie a tale obbligo, "in caso di controversia verrà ammesso come prova il controllo effettuato dal collaboratore". Questa norma non comporta un vero e proprio rovesciamento dell'onere della prova, com'era invece il caso sotto l'egida del precedente CCNL (cfr. sentenza 4C.7/2004 dell'8 marzo 2004 consid. 2.2.3); essa attribuisce al controllo effettuato dal lavoratore valenza probatoria e non solo di allegazione di parte (sentenza 4A_86/2008 del 23 settembre 2008 consid. 4.2; STREIFF/VON KAENEL, Arbeitsvertrag, 6a ed. 2006, n. 10 ad <ref-law>).
Da quanto qui esposto discende che, in assenza di un controllo dell'orario di lavoro effettivo da parte del ricorrente, il Tribunale d'appello poteva, giusta l'art. 21 n. 3 CCNL, la cui applicabilità alla fattispecie non è contestata, riferirsi al conteggio versato agli atti dall'opponente per determinare il numero di ore supplementari da questa eseguite, ritenuto segnatamente che nella sede federale il ricorrente non indica un qualsiasi elemento da lui apportato per confutare il computo allestito dalla dipendente.
6. Si rivela infine inammissibile, perché non soddisfa le esigenze di motivazione per una valida censura degli accertamenti di fatto contenuti nella sentenza impugnata (supra, consid. 2.1), la non meglio specificata lamentela del ricorrente secondo cui la Corte cantonale avrebbe ritenuto, con riferimento ai giorni festivi in cui l'opponente ha lavorato, una situazione contraria a quella emersa dalle tavole processuali.
7. Da quanto precede discende che il ricorso, nella ridotta misura in cui risulta ammissibile, si appalesa infondato e come tale va respinto. Le spese giudiziarie, determinate sulla base della tariffa ridotta dell'art. 65 cpv. 4 lett. c LTF, e le ripetibili seguono la soccombenza (art. 66 cpv. 1 e 68 cpv. 1 LTF).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. Le spese giudiziarie di fr. 600.-- sono poste a carico del ricorrente, che rifonderà all'opponente fr. 1'000.-- a titolo di ripetibili per la sede federale.
3. Comunicazione ai patrocinatori delle parti e alla II Camera civile del Tribunale d'appello del Cantone Ticino.