Fatti:
A. Alle dipendenze della ditta B._SA - in qualità di autista - dal 12 gennaio 2004, A._ ha cessato la propria attività il 7 febbraio 2006, data a partire dalla quale egli è stato inabile al lavoro al 100 % per malattia.
A.a Lo stesso giorno B._SA ha disdetto il rapporto di lavoro con effetto al 30 aprile 2006, termine poi prorogato sino al 31 luglio 2006. Nello scritto indirizzato a A._ essa gli ha fra l'altro comunicato che con l'uscita dal contratto di lavoro scadeva anche l'assicurazione collettiva contro incidente e malattia stipulata con C._ e ch'egli aveva la "possibilità di stipulare un'assicurazione indennità perdita di guadagno giornaliera singola con la nostra o tramite la vostra cassa malati privata".
A.b Interpellata dall'assicurato, il 1° settembre 2006 C._ lo ha informato che il suo diritto alle prestazioni contrattuali sarebbe giunto al termine, al più tardi, il 29 ottobre 2006, ovvero 90 giorni dopo la fine del rapporto di lavoro.
B. Asserendo che C._ gli aveva rifiutato il passaggio nell'assicurazione individuale perché il contratto d'assicurazione stipulato da B._SA non prevedeva una simile possibilità per gli impiegati - come lui - al beneficio di un permesso di lavoro per confinanti (frontalieri), il 7 febbraio 2007 A._ ha convenuto l'ex datrice di lavoro dinanzi alla Pretura del Distretto di Lugano, onde ottenere il pagamento di fr. 11'208.65, pari a quanto avrebbe percepito durante i mesi ottobre 2006-gennaio 2007 se essa avesse stipulato una copertura assicurativa conforme a quanto pattuito nel contratto di lavoro.
Convinta di aver perfettamente adempiuto ai propri obblighi, B._SA ha avversato la richiesta di A._, il quale avrebbe semmai dovuto - a suo modo di vedere - contestare la decisione di C._.
Statuendo il 14 agosto 2008, il Pretore ha integralmente accolto l'istanza di A._.

Considerato che, conformemente alle indicazioni contenute nella lettera di disdetta e alle clausole contrattuali, egli aveva comunicato all'assicurazione perdita di guadagno del datore di lavoro la volontà di effettuare il passaggio dall'assicurazione collettiva a quella individuale e che nelle promesse di copertura contenute nel contratto di lavoro B._SA aveva garantito questa possibilità, il giudice ha deciso che, indipendentemente dai motivi precisi per cui C._ aveva rifiutato il passaggio, alla datrice di lavoro era in ogni caso imputabile un'inadempienza contrattuale, ragione per cui l'ha condannata a risarcire il danno cagionato al lavoratore.
C. Adita da B._SA, con sentenza dell'8 ottobre 2008 la II Camera civile del Tribunale d'appello del Cantone Ticino ha rovesciato la pronunzia di primo grado.
I giudici della massima istanza cantonale hanno stabilito che, "diversamente da quanto ritenuto dal Pretore, i motivi dell'eventuale diniego della compagnia assicurativa del passaggio dall'assicurazione collettiva a quella individuale sono di fondamentale importanza, perché da essi si ricava se vi sia stata omissione, e quindi responsabilità del datore di lavoro a norma dell'<ref-law> (copertura assicurativa conforme al contratto di lavoro) o omissione del lavoratore (per esempio ritardo nel postulare il passaggio suddetto)". L'alta Corte ticinese non ha tuttavia potuto procedere a un esame della fattispecie sotto questo profilo perché "agli atti non sono presenti - non essendo stati prodotti o richiamati documenti, neppure in edizione - né la polizza di assicurazione collettiva di malattia [...] né le condizioni generali [...]. Non è dunque dato di sapere se la polizza in questione sia stata stipulata in base alla LCA o alla LAMal; neppure sono note le condizioni regolanti il diritto alle prestazioni e l'eventuale passaggio dall'assicurazione collettiva a quella individuale." In queste circostanze, ha concluso il Tribunale d'appello, non è possibile determinarsi su eventuali responsabilità del datore di lavoro. Donde la riforma del giudizio pretorile nel senso della reiezione dell'istanza di A._ per carenza di prove.
D. Prevalendosi della violazione della massima inquisitoria sociale consacrata dall'<ref-law> e della violazione del divieto dell'arbitrio sancito dall'<ref-law>, il 12 novembre 2008 A._ è insorto dinanzi al Tribunale federale con un ricorso ordinario simultaneo giusta l'<ref-law>, teso in sostanza alla modifica della sentenza cantonale nel senso di un rinvio degli atti al Pretore per esperire l'istruttoria.
Nelle osservazioni del 15 gennaio 2009 B._SA propone di dichiarare i ricorsi inammissibili rispettivamente di respingerli. L'autorità cantonale non si è invece determinata.
Diritto:
1. Il Tribunale federale si pronuncia d'ufficio e con pieno potere d'esame sulla propria competenza e sull'ammissibilità del rimedio esperito (<ref-law>; <ref-ruling> consid. 1.1 pag. 3).
1.1 Preliminarmente va osservato che il ricorrente ha introdotto un ricorso ordinario simultaneo, giusta l'<ref-law>, nell'errata convinzione che la via del rimedio ordinario (il ricorso in materia civile) sia aperta solo per censurare la violazione del diritto privato federale e che l'applicazione del diritto costituzionale possa essere criticata solo con il ricorso sussidiario in materia costituzionale. Non è così.
Con il ricorso in materia civile può infatti essere fatta valere la violazione del diritto federale (<ref-law>), che include anche i diritti costituzionali dei cittadini (<ref-ruling> consid. 3.1, 462 consid. 2.3). Solo se il ricorso in materia civile non è proponibile, entra in linea di conto il ricorso - sussidiario, appunto - in materia costituzionale (<ref-law>) per violazione di diritti costituzionali (<ref-law>).
Sia come sia, nella fattispecie in esame la decisione d'introdurre i due rimedi simultaneamente appare adeguata in considerazione dell'esiguo valore litigioso della causa, che ostacola effettivamente la ricevibilità del rimedio ordinario.
1.2 Pronunciata nel quadro di una causa civile (<ref-law>) di carattere pecuniario in materia di diritto del lavoro, il cui valore litigioso non raggiunge l'importo minimo di fr. 15'000.-- prescritto dall'<ref-law>, la decisione cantonale può infatti essere impugnata con un ricorso in materia civile solo se la controversia concerne una questione di diritto d'importanza fondamentale (<ref-law>).
1.2.1 A mente del ricorrente questo requisito è in concreto soddisfatto perché viene asseverata la violazione della massima inquisitoria sociale di cui all'<ref-law>.
1.2.2 Ciò non basta tuttavia per ammettere una questione di diritto d'importanza fondamentale ai sensi dell'<ref-law>.
Secondo la giurisprudenza sviluppata dal Tribunale federale dopo l'entrata in vigore della LTF, la nozione di "questione di diritto d'importanza fondamentale" dev'essere interpretata in maniera molto restrittiva (<ref-ruling> consid. 1.1). Le situazioni nelle quali è già stata ammessa l'esistenza di una "questione di diritto d'importanza fondamentale" sono elencate nella <ref-ruling> consid. 1.3 pag. 4; in breve, è considerata questione di diritto d'importanza fondamentale quella che crea una situazione d'incertezza giuridica tale da rendere urgentemente necessario un chiarimento da parte del Tribunale federale (sentenza 4A_14/2009 del 2 aprile 2009 consid. 1, destinato a pubblicazione). Incombe alla parte ricorrente il compito di esporre le ragioni per le quali la questione giuridica da lui sollevata è d'importanza fondamentale nel senso appena esposto (art. 42 cpv. 2 seconda frase LTF; <ref-ruling> consid. 1.2). La generica affermazione del ricorrente non soddisfa questa esigenza di motivazione.
1.2.3 A ogni modo, la controversia non riguarda una questione giuridica d'importanza fondamentale nel senso dell'<ref-law>, giacché il Tribunale federale si è già più volte espresso in merito alla portata della massima inquisitoria sociale - nel diritto del lavoro (fra tutte <ref-ruling> consid. 2) e nel diritto della locazione (<ref-ruling> consid. 4a pag. 238) - e il litigio verte sull'applicazione dei principi giurisprudenziali nel caso in rassegna (<ref-ruling> consid. 1.2).
Il ricorso in materia civile non è pertanto proponibile.
1.3 La sentenza del Tribunale d'appello può dunque essere impugnata solo con un ricorso sussidiario in materia costituzionale (<ref-law>).
1.3.1 Rivolto contro una decisione finale (art. 117 e 90 LTF) pronunciata dall'autorità ticinese di ultima istanza (art. 114 e art. 75 cpv. 1 LTF) e presentato - nei termini legali (art. 117 e 100 cpv. 1 LTF) - dalla parte le cui conclusioni sono state disattese in sede cantonale e che ha di conseguenza un interesse legittimo all'annullamento o alla modifica della decisione (<ref-law>), il gravame risulta ricevibile.
1.3.2 Con il ricorso in materia costituzionale può unicamente essere censurata la violazione dei diritti costituzionali (<ref-law>).
1.3.3 Giusta l'<ref-law> combinato con l'<ref-law> (cui rinvia l'<ref-law>), l'atto di ricorso deve indicare chiaramente quali sarebbero i diritti costituzionali violati nella decisione cantonale e precisare in cosa consisterebbe tale violazione (<ref-ruling> consid. 6).
1.3.3.1 In particolare, qualora venga lamentata una violazione del divieto d'arbitrio (<ref-law>) non ci si può limitare a criticare la pronunzia 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ì occorre dimostrare, attraverso un'argomentazione chiara e dettagliata, che la decisione impugnata è arbitraria (<ref-ruling> consid. 4.1 pag. 589).
Per giurisprudenza invalsa, pertinentemente evocata nel gravame, infatti, 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. 2.1 con rinvii).
1.3.3.2 In concreto, il ricorrente rimprovera alla Corte cantonale di essere incorsa nell'arbitrio - vietato dall'<ref-law> - riformando il giudizio pretorile nel senso della reiezione dell'istanza per carenza di prove (<ref-law>), invece di rinviare gli atti al Pretore affinché procedesse all'istruttoria di causa, così come previsto dalla massima inquisitoria sociale sancita dall'<ref-law>.
Secondo l'opponente l'argomentazione ricorsuale, così come formulata, non ossequia i requisiti di motivazione sopra esposti e propone pertanto di dichiarare il gravame inammissibile.
In effetti, il tenore dell'allegato sottoposto all'esame del Tribunale federale suscita delle perplessità sotto il profilo della motivazione; si può nondimeno concedere che il ricorrente ha indicato in maniera sufficientemente chiara e dettagliata i motivi per i quali invoca la violazione del divieto dell'<ref-law>, come esposto qui di seguito.
2. La II Camera civile del Tribunale d'appello ha ritenuto impossibile determinarsi su eventuali responsabilità dell'opponente a causa delle gravi carenze probatorie riscontrate nell'istruttoria di prima istanza. L'alta Corte ticinese ha escluso di esperire essa medesima le prove idonee ai fini del giudizio, in applicazione della massima ufficiale e del principio inquisitorio, tale facoltà essendo limitata ai casi in cui sia necessario completare l'istruttoria eseguita dal primo giudice e non esperire l'istruttoria vera e propria completamente dimenticata in prima sede; non spetta infatti a lei istruire la causa per la prima volta, sostituendosi al giudice naturale. Ciò vale a maggior ragione se, come nel caso in esame, il lavoratore è stato rappresentato dal servizio giuridico di un sindacato.
Come anticipato, dinanzi al Tribunale federale non viene criticata la mancata assunzione delle prove in sede d'appello bensì il mancato rinvio della causa al Pretore, che il Tribunale d'appello non sembra aver preso in considerazione. A mente del ricorrente, riformando la pronunzia pretorile nel senso della reiezione della sua istanza per carenza di prove, la Corte cantonale avrebbe "sacrificato la massima inquisitoria in nome dell'onere della prova" e pronunciato una sentenza in manifesto contrasto con la massima inquisitoria sociale, che le imponeva invece di rinviare la causa per nuova istruzione probatoria. Richiamandosi alla dottrina e alla giurisprudenza, anche a quella vigente in Ticino, egli sostiene infatti che, in una procedura retta dalla massima inquisitoria sociale, com'è quella in esame, qualora la seconda istanza constati lacune importanti nell'istruttoria effettuata dal giudice di primo grado, essa non respinge l'azione per carenza di prove bensì annulla la pronunzia di primo grado e rinvia la causa al giudice inferiore.
3. L'<ref-law> stabilisce che nelle controversie derivanti dal rapporto di lavoro il cui valore litigioso non superi fr. 30'000.--, il giudice accerta d'ufficio i fatti e apprezza liberamente le prove.
3.1 La massima inquisitoria sociale sancita da questa norma riguarda la raccolta del materiale probatorio - ovvero l'accertamento dei fatti rilevanti ai fini del giudizio - dinanzi al giudice di prima istanza, (sentenza 4C.340/2004 del 2 dicembre 2004 consid. 4.1, non pubblicato in <ref-ruling>), non invece l'oggetto della controversia, che resta nella libera disposizione delle parti. Queste rimangono tenute a esporre - nei modi e nei tempi stabiliti dalle norme procedurali applicabili - le circostanze all'origine delle loro pretese e a indicare i mezzi di prova disponibili (<ref-ruling> consid. 2.2 pag. 107; <ref-ruling> consid. 2c; cfr. anche, seppur riferita a una controversia in materia di locazione, <ref-ruling> consid. 4a pag. 238 e 239). Se ha oggettivamente motivo di dubitare della completezza delle allegazioni di fatto e dei mezzi di prova offerti, il giudice è tuttavia tenuto a interpellare le parti (<ref-ruling> consid. 2c; sentenza 4P.297/2001 del 26 marzo 2002 consid. 2c; Tobler/Favre/Munoz/Ehm, Arbeitsrecht, 2006, n. 4.2 ad <ref-law>) e, secondo parte della dottrina, può anche convocare di propria iniziativa dei testimoni e/o ordinare l'edizione di documenti (Hans-Peter Egli, Das arbeitsrechtliche Verfahren nach <ref-law> in zzz 2004 pag. 21 segg., in particolare pag. 43 e n. 225 con numerosi riferimenti dottrinali).
3.2 Nella fattispecie in rassegna, sin dall'inizio del procedimento giudiziario il ricorrente ha sostenuto di non aver potuto passare all'assicurazione individuale perché la copertura assicurativa stipulata dall'opponente - contrariamente a quanto pattuito nel contratto di lavoro - non contemplava una simile possibilità per i lavoratori frontalieri. L'oggetto del litigio è stato così chiaramente fissato: il ricorrente ha rimproverato all'opponente il mancato adempimento dell'obbligo assunto nel contratto di lavoro di stipulare un'assicurazione che gli garantisse questa possibilità.
Come rettamente stabilito dai giudici ticinesi egli, gravato dall'onere probatorio in virtù dell'<ref-law>, doveva dimostrare (i) l'esistenza di un obbligo contrattuale dell'opponente a questo riguardo, (ii) di essersi tempestivamente rivolto all'assicurazione per effettuare il passaggio all'assicurazione individuale e (iii) che ciò gli era stato negato a causa di una mancanza dell'opponente. Il giudice di primo grado ha reputato dimostrate le prime due condizioni e irrilevante l'ultima. A torto. I giudici d'appello hanno ragione quando affermano che il motivo per il quale l'assicurazione ha respinto la richiesta del ricorrente è determinante ai fini del giudizio sulla responsabilità dell'opponente e, quindi, sulla pretesa di A._. Essi hanno pure ragione quando spiegano che, in assenza della polizza di assicurazione collettiva di malattia e delle condizioni generali di assicurazione applicabili - così come della corrispondenza intercorsa fra il ricorrente e l'assicurazione in merito alla sua richiesta di passaggio all'assicurazione individuale, rispettivamente di una testimonianza a questo riguardo - non è possibile determinarsi sulla responsabilità dell'opponente.
3.3 Nulla può essere rimproverato ai giudici del Tribunale d'appello per non aver istruito loro stessi la causa, giacché il diritto federale impone il rispetto della massima inquisitoria sociale in prima istanza, mentre lascia i Cantoni liberi di stabilire le regole da applicare in seconda istanza (<ref-ruling> consid. 3 pag. 237).
Non è dato per contro di sapere per quale motivo l'alta Corte ticinese, pur avendo constatato l'assenza di "un'istruttoria vera e propria", precisando addirittura che questa è stata "completamente dimenticata in prima sede", abbia d'acchito scartato l'eventualità di rinviare la causa al Pretore per esperire l'istruttoria, già ammessa in dottrina (cfr. Tobler/Favre/Munoz/Ehm, op.cit, n. 4.3 ad art. 343) e a livello cantonale (JAR 1996 pag. 352-354 [FR, Tribunal cantonal]). Nella sentenza impugnata questo tema non è stato trattato.
3.4 Il richiamo del ricorrente alla giurisprudenza ticinese - che dispone il rinvio della causa al giudice di primo grado quando viene constatata un'istruttoria carente - non si attaglia bene alla fattispecie in esame, siccome riferita a procedimenti concernenti i contributi di mantenimento per figli minorenni, nell'ambito dei quali - nonostante il tenore praticamente identico delle due norme (<ref-law> e <ref-law>) - la giurisprudenza riconosce alla massima inquisitoria una portata più ampia (cfr. <ref-ruling> consid. 3.2.1).
Come già spiegato al consid. 3.1, nel quadro dei procedimenti retti dalla massima inquisitoria sociale (<ref-law>) il giudice è tenuto a interpellare le parti circa la completezza dei mezzi di prova da loro offerti solo se ha oggettivamente motivo di dubitarne (<ref-ruling> consid. 2c). Inoltre, dato che la massima inquisitoria sociale è stata introdotta allo scopo di facilitare la comparsa dinanzi all'autorità giudiziaria alle persone non patrocinate, la giurisprudenza attenua di principio l'obbligo del giudice d'interpellare le parti quando queste sono assistite da un avvocato (cfr. sentenza 4C.395/2005 del 1° marzo 2006 consid. 4.3 e 4C.392/1999 dell'11 febbraio 2000 consid. 2c; Hans-Peter Egli, op. cit., pag. 43). Da questo non si può tuttavia dedurre ch'essa non ha la benché minima valenza qualora una parte sia assistita da un legale o, come nel caso in esame, da un'associazione professionale. Una simile conclusione svuoterebbe praticamente di significato l'<ref-law>.
Nella fattispecie in rassegna, la Corte cantonale ha stabilito che l'istruttoria effettuata in prima sede è stata "completamente dimenticata" e che ciò va ricondotto non solo al comportamento delle parti, le quali hanno prodotto solo pochi documenti, "con scarsa valenza probatoria", ma anche all'errata valutazione giuridica della fattispecie da parte del giudice di primo grado, il quale - a torto - ha reputato irrilevanti i motivi che hanno spinto l'assicurazione a negare al ricorrente il passaggio all'assicurazione individuale. Ora, qualora il giudice avesse valutato correttamente la fattispecie, avrebbe ravvisato la chiara insufficienza dei mezzi di prova offerti dalle parti su questo punto decisivo ai fini del giudizio e, di conseguenza, le avrebbe interpellate così come prescritto dall'<ref-law>, invitandole a completare i mezzi di prova. Egli non avrebbe per contro proceduto di sua iniziativa a un'assunzione di mezzi di prova, essendo le parti patrocinate.
Tenuto conto delle particolari circostanze del caso concreto, appena descritte, la decisione dei giudici cantonali di escludere senza alcuna spiegazione il rinvio della causa al primo giudice e di riformare invece la pronunzia pretorile nel senso della reiezione dell'istanza per carenza di prove lede gravemente la massima inquisitoria sociale e risulta in contraddizione urtante con il sentimento della giustizia e dell'equità.
4. La sentenza impugnata va pertanto annullata per violazione dell'<ref-law>
4.1 In accoglimento del ricorso sussidiario in materia costituzionale, il punto I della sentenza cantonale deve venir annullato e modificato nel senso di un rinvio della causa al giudice di primo grado per istruzione e nuovo giudizio. In simili circostanze il Tribunale federale può tuttavia, in applicazione dell'art. 107 cpv. 2 seconda frase LTF, rinviare direttamente la causa al Pretore del Distretto di Lugano, sezione 2.
Dato che l'appello dell'opponente - tendente all'annullamento della pronunzia pretorile e alla reiezione dell'azione - viene comunque parzialmente accolto, l'importo di fr. 400.-- riconosciuto dai giudici cantonali all'opponente a titolo di ripetibili d'appello può essere confermato.
4.2 Le spese giudiziarie e le ripetibili della sede federale seguono la soccombenza (art. 66 cpv. 1 e 68 cpv. 1 e 2 LTF). Infatti, 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.--. Poiché il valore di causa non supera fr. 30'000.-- l'importo delle spese giudiziarie è tuttavia ridotto (art. 65 cpv. 4 lett. c LTF). Lo stesso non vale per le ripetibili.

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso in materia civile è inammissibile.
2. Il ricorso sussidiario in materia costituzionale è accolto.
Di conseguenza il pto I del dispositivo della sentenza emanata l'8 ottobre 2008 dalla II Camera civile del Tribunale d'appello del Cantone Ticino viene annullato e la causa rinviata alla Pretura del Distretto di Lugano per istruzione e nuovo giudizio nel senso dei considerandi. Il pto II del dispositivo della sentenza impugnata viene invece confermato.
3. Le spese giudiziarie di fr. 500.-- sono poste a carico dell'opponente, la quale rifonderà al ricorrente fr. 2'000.-- per ripetibili della sede federale.
4. Comunicazione ai patrocinatori delle parti e alla II Camera civile del Tribunale d'appello del Cantone Ticino.