Fatti:
A. Il 10 giugno 2008 è apparso sul Foglio ufficiale del Cantone Ticino il bando di concorso per l'assunzione segnatamente di un docente di sostegno pedagogico presso le scuole comunali di Chiasso, che sarebbe stato nominato a metà tempo. L'avviso elencava i requisiti che i candidati dovevano adempiere ed esigeva tra l'altro il certificato rilasciato dall'Istituto cantonale di abilitazione o dall'Alta scuola pedagogica, oppure il certificato di superamento della prova di assunzione, oppure ancora la dichiarazione di validità dei titoli ai fini dell'assunzione anche senza abilitazione. Al concorso hanno partecipato 29 candidati, tra cui A._ e B._.
B. Il 29 luglio 2008 il Municipio di Chiasso ha risolto di assumere A._ quale docente nominato a metà tempo. Gli ha quindi comunicato la decisione, ricordandogli che era riservata la facoltà di ricorso, nei termini di legge, ad ogni persona lesa direttamente nei suoi legittimi interessi. Il Municipio ha contestualmente comunicato a B._ la sua mancata assunzione.
C. B._ si è aggravata contro la risoluzione municipale dinanzi al Consiglio di Stato del Cantone Ticino, che con decisione del 24 settembre 2008 ha parzialmente accolto il gravame. Il Governo ha rilevato che A._ non aveva conseguito l'abilitazione all'insegnamento, necessaria per esercitare la professione di docente nelle scuole pubbliche del Cantone: egli non poteva quindi occupare un posto per il quale era prevista una nomina, ma poteva soltanto partecipare ai concorsi per incarichi fino agli anni 2010-2011. Il Governo ha pertanto annullato la risoluzione impugnata e ha rinviato gli atti al Municipio perché riapra il concorso o proceda a una nuova nomina sulla base delle candidature valide inoltrate.
D. A._ impugna questa decisione con un ricorso in materia di diritto pubblico e un ricorso sussidiario in materia costituzionale davanti al Tribunale federale, chiedendo in via principale di annullarla e di confermare la sua nomina quale docente di sostegno pedagogico a metà tempo. In via subordinata, chiede di essere incaricato in tale qualità fino al conseguimento dell'abilitazione in occasione del prossimo corso indetto dall'Alta scuola pedagogica. In via ulteriormente subordinata postula l'annullamento della decisione impugnata affinché sulla fattispecie statuisca innanzitutto il Dipartimento dell'educazione, della cultura e dello sport. Il ricorrente lamenta in sostanza la violazione degli art. 5, 9 e 29 Cost.
E. Invitati ad esprimersi sul gravame, il Consiglio di Stato e il Municipio di Chiasso si rimettono al giudizio del Tribunale federale. Il Governo cantonale ribadisce comunque che l'abilitazione all'insegnamento è la condizione indispensabile prevista dalla legge per esercitare l'attività di docente di sostegno pedagogico nelle scuole elementari. B._ e il Dipartimento dell'educazione, della cultura e dello sport (Dipartimento) postulano invece la reiezione dei ricorsi.
Con decreto presidenziale del 19 novembre 2008 è stato conferito al gravame l'effetto sospensivo.

Diritto:
1. 1.1 Il Tribunale federale esamina d'ufficio e con piena cognizione la sua competenza (cfr. art. 29 cpv. 1 LTF) e l'ammissibilità dei gravami che gli vengono sottoposti (<ref-ruling> consid. 1, 186 consid. 1).
1.2 Il ricorso in materia di diritto pubblico, pur se entro certo limiti (art. 85 cpv. 1 lett. b LTF), è di massima ammissibile contro le decisioni in materia di rapporti di lavoro di diritto pubblico concernenti controversie patrimoniali (cfr. art. 82 lett. a in relazione con l'art. 83 lett. g LTF). La decisione impugnata concerne un rapporto di lavoro di diritto pubblico: il ricorrente non chiede tuttavia il versamento di una somma di denaro, postulando piuttosto la conferma della sua nomina nella funzione di docente di sostegno pedagogico. Ritenuto che la richiesta persegue comunque, perlomeno parzialmente, uno scopo economico e nella misura in cui il suo oggetto può essere valutato in denaro, la controversia assume natura patrimoniale. Il motivo di esclusione dell'art. 83 lett. g LTF non entra quindi in considerazione (cfr. sentenza 1C_116/2007 del 24 settembre 2007, consid. 2). Trattandosi di una nomina a tempo indeterminato, per la quale è prevista una specifica classe di stipendio, il valore litigioso minimo di fr. 15'000.-- previsto dall'art. 85 cpv. 1 lett. b LTF è manifestamente raggiunto (cfr. art. 51 cpv. 2 LTF). Giova nondimeno ricordare che, a norma dell'art. 112 cpv. 1 lett. d LTF, in una decisione impugnabile davanti al Tribunale federale il valore litigioso deve esservi menzionato.
1.3 Il ricorrente ha partecipato al procedimento ed è particolarmente toccato dalla decisione impugnata, che annulla la nomina decisa dal Municipio di Chiasso. Egli ha un interesse degno di protezione al suo annullamento o alla sua modifica ed è quindi legittimato a ricorrere (art. 89 cpv. 1 LTF). La decisione impugnata rinvia gli atti al Municipio per la riapertura del concorso o la nomina di un altro candidato. Nei confronti del ricorrente essa pone tuttavia fine al procedimento, siccome, nelle circostanze attuali, lo esclude definitivamente dalla nomina, non lasciando al riguardo alcun margine di apprezzamento all'esecutivo comunale. Il provvedimento impugnato deve quindi essere considerato alla stregua di una decisione finale giusta l'art. 90 LTF. Il Consiglio di Stato ha in concreto statuito in modo definitivo quale autorità cantonale di ultima istanza (cfr. art. 86 cpv. 1 lett. d LTF). Esso non è invero un'autorità giudiziaria, ma il ricorrente non pretende che la causa debba essere giudicata da un Tribunale superiore cantonale, l'art. 130 cpv. 3 LTF lasciando d'altra parte ai Cantoni un termine di due anni dall'entrata in vigore della LTF per emanare le disposizioni di esecuzione dell'art. 86 cpv. 2 LTF. Tempestivo (art. 100 cpv. 1 LTF), il ricorso in materia di diritto pubblico è pertanto ammissibile. Il ricorso sussidiario in materia costituzionale ai sensi dell'art. 113 segg. LTF è conseguentemente inammissibile.
2. 2.1 Il ricorrente lamenta innanzitutto una violazione del principio della legalità, sostenendo che la risoluzione governativa impugnata sarebbe illegale, siccome il compito di annullare o riformare la decisione municipale non sarebbe spettato al Consiglio di Stato, bensì in primo luogo al Dipartimento, secondo quanto prevederebbe l'art. 10 della legge ticinese della scuola, del 1° febbraio 1990 (Lsc). Rimprovera alla precedente istanza di averlo quindi privato a torto del doppio grado di giurisdizione.
2.2 Secondo la giurisprudenza concernente il previgente art. 84 cpv. 1 lett. a OG, all'infuori del campo del diritto penale e di quello in materia di tributi pubblici, il principio della legalità non costituisce un diritto costituzionale con portata propria, ma un principio costituzionale che può essere invocato solo in relazione con un diritto fondamentale specifico (<ref-ruling> consid. 3a e riferimenti). È quindi dubbio che, sollevata come in concreto a titolo indipendente, la censura di violazione del principio della legalità sia proponibile. Tuttavia, quand'anche si volesse ritenerla ammissibile, la conseguenza per il Tribunale federale non sarebbe quella di potere esaminare liberamente il diritto cantonale. Ad eccezione di determinati casi, che non entrano qui in considerazione, la semplice violazione del diritto cantonale non costituisce infatti un motivo di ricorso previsto dall'art. 95 LTF (cfr. sentenza 2C_212/2007 dell'11 dicembre 2007, consid. 3.1), sicché in questo ambito il potere cognitivo del Tribunale federale rimane limitato all'arbitrio (<ref-ruling> consid. 1.2.1, 133 I 201 consid. 1).
Invocando il principio della legalità, il ricorrente lamenta sostanzialmente la violazione dell'art. 10 cpv. 2 lett. h Lsc, secondo cui al Dipartimento, che esercita la direzione generale della scuola, spetta in particolare il compito di riformare o annullare, su istanza o d'ufficio, le decisioni di autorità comunali o consortili e degli organi scolastici cantonali non conformi ai principi fondamentali del diritto, alle legge e ai regolamenti scolastici. Questa disposizione non disciplina tuttavia la funzione di autorità di ricorso del Dipartimento, che è regolata sotto il titolo riservato al contenzioso, agli art. 92 segg. Lsc (cfr. messaggio del Consiglio di Stato del 30 giugno 1987 sulla legge della scuola, commento all'art. 10). Al riguardo, il ricorso al Dipartimento è previsto unicamente contro le decisioni degli organi scolastici cantonali e degli organi preposti alla conduzione degli istituti (art. 92 Lsc). L'art. 94 Lsc prevede invece esplicitamente che contro le decisioni dei municipi è dato ricorso al Consiglio di Stato. Non si può quindi ragionevolmente rimproverare a quest'ultima autorità di essere incorsa nell'arbitrio per essere entrata nel merito dell'impugnativa presentata da B._ contro la risoluzione municipale.
3. 3.1 Il ricorrente sostiene che la sua candidatura sarebbe stata conforme al bando di concorso e che l'Ufficio delle scuole comunali del competente Dipartimento gli ha comunicato il superamento della prova di assunzione, autorizzandolo esplicitamente a partecipare ai concorsi, senza alcuna riserva. Ritiene che, rifiutandogli in sede di ricorso di riconoscergli la nomina, l'autorità cantonale avrebbe disatteso le condizioni da essa medesima fissate, comportandosi in modo contraddittorio e violando sia il principio dell'affidamento sia il divieto dell'arbitrio.
3.2 L'art. 9 Cost. istituisce un diritto fondamentale del cittadino ad essere trattato secondo il principio della buona fede da parte degli organi dello Stato. In materia di diritto amministrativo, tale principio tutela l'amministrato nei confronti dell'autorità, quando, assolte determinate condizioni, il medesimo abbia agito conformemente alle istruzioni e alle dichiarazioni di quest'ultima. Il principio tutela in particolare la fiducia riposta in un'informazione ricevuta dall'autorità o in suo determinato comportamento suscettibile di destare un'aspettativa legittima, quando l'autorità sia intervenuta in una situazione concreta riguardo a determinate persone, quand'essa era competente a rilasciare l'informazione o il cittadino poteva ritenerla competente sulla base di fondati motivi, quando affidandosi all'esattezza dell'informazione egli abbia preso delle disposizioni non reversibili senza subire un pregiudizio e quando non siano intervenuti mutamenti legislativi posteriori al rilascio dell'informazione stessa (<ref-ruling> consid. 8.1 pag. 60, 129 II 361 consid. 7.1, 129 I 161 consid. 4.1 e rinvii).
3.3 Giusta l'art. 7 della legge cantonale sull'ordinamento degli impiegati dello Stato e dei docenti, del 15 marzo 1995 (LOrd), la quale disciplina pure il rapporto d'impiego dei docenti delle scuole comunali (art. 52 Lsc in relazione con l'art. 1 cpv. 1 lett. b LOrd), la nomina è l'atto amministrativo con cui il dipendente viene assunto a tempo indeterminato e assegnato a una funzione. Essa è subordinata ai titoli di studio e ai requisiti di età, di idoneità e di preparazione contemplati nella descrizione della funzione individuale e pubblicati nel bando di concorso (art. 8 cpv. 1 LOrd). Secondo l'art. 15 LOrd, l'incarico è invece l'atto amministrativo con cui il dipendente viene assegnato ad una funzione per un periodo determinato. Esso è conferito in luogo della nomina in una serie di casi determinati (art. 16 LOrd), segnatamente quando, in difetto di concorrenti idonei, si debba ricorrere a candidati sprovvisti dei requisiti di nomina (art. 16 lett. c LOrd).
In concreto, il bando di concorso elencava i posti di lavoro per docenti di sostegno pedagogico messi a concorso in diversi Comuni del Cantone Ticino, per i quali erano previsti nomine o incarichi, specificando che a Chiasso era prevista una nomina a metà tempo. I requisiti richiesti ai candidati erano esposti in modo generale, senza distinzione tra le assunzioni con nomina e per incarico e in particolare senza specificare che l'abilitazione all'insegnamento costituiva una condizione necessaria per la nomina. Nemmeno la lettera del 4 maggio 2007 con cui l'Ufficio delle scuole comunali comunicava al ricorrente il superamento della prova di assunzione quale docente di sostegno pedagogico specificava tale requisito, autorizzandolo genericamente a partecipare ai concorsi fino all'anno scolastico 2010/2011. Certo, chi non adempie i requisiti per una nomina può di principio partecipare anche a un concorso per un posto che la prevede, potendo essergli conferito un incarico qualora manchino candidati idonei per la nomina (cfr. art. 16 lett. c LOrd). Tuttavia, fondandosi sul bando di concorso e sulla suddetta lettera dell'autorità cantonale, che non operavano distinzioni di sorta, il ricorrente poteva essere indotto in buona fede a ritenere di partecipare ai concorsi con l'eventualità di essere assunto senza limitazioni, quindi anche mediante una nomina.
Le autorità competenti non gli hanno però assicurato ch'egli sarebbe stato assunto. Il Municipio gli ha infatti esplicitamente ricordato, contestualmente alla comunicazione della decisione di nominarlo quale docente di sostegno pedagogico a metà tempo, che era ancora riservata la facoltà di ricorso ad ogni persona lesa direttamente nei suoi legittimi interessi. Non risulta del resto che in seguito alle informazioni fornite dalle autorità egli ha preso delle disposizioni difficilmente revocabili, per esempio disdicendo un contratto di lavoro anteriore. Né il ricorrente lo sostiene, precisando per contro di essere stato precedentemente disoccupato. Comunque, egli non avrebbe potuto prendere simili disposizioni in buona fede, ritenuto che l'esito del concorso era incerto prima che il Municipio si pronunciasse sulle candidature e che anche in seguito la situazione permaneva incerta, siccome un'assunzione definitiva non gli era comunque stata assicurata, essendogli peraltro noto l'avvio di una procedura ricorsuale (cfr. sentenza 2P.10/2002 del 17 giugno 2002, consid. 2.3). In sostanza, sulla base del tenore del bando di concorso e della lettera 4 maggio 2007 dell'autorità scolastica cantonale, il ricorrente ha semplicemente partecipato al concorso con l'aspettativa di potere essere anche nominato e non soltanto incaricato, ritenendo per finire di avere maggiori possibilità di essere assunto rispetto a quelle che erano verosimilmente le reali probabilità. Le autorità non hanno però adottato nei suoi confronti un comportamento contraddittorio per quanto concerne la decisione di assumerlo e non hanno pertanto disatteso né il principio della buona fede né il divieto dell'arbitrio.
4. 4.1 Il ricorrente sostiene che la decisione impugnata sarebbe sproporzionata siccome richiede il conseguimento dell'abilitazione all'insegnamento anche per docenti di sostegno pedagogico, che in realtà non svolgerebbero l'attività di insegnante, bensì una consulenza psicosociale. A suo dire, il Consiglio di Stato prevederebbe in futuro di abolire tale requisito per i candidati che, come lui, sarebbero in possesso di un diploma universitario in pedagogia.
4.2 Sollevando la censura di violazione del principio della proporzionalità senza relazione con un diritto fondamentale specifico, il ricorrente disattende che il Tribunale federale esamina l'applicazione del diritto cantonale sotto il profilo ristretto dell'arbitrio (<ref-ruling> consid. 4). Spettava quindi al ricorrente spiegare con una motivazione conforme agli art. 42 cpv. 2 e 106 cpv. 2 LTF per quali ragioni la decisione impugnata sarebbe non soltanto discutibile, ma addirittura arbitraria (cfr., sulle esigenze di motivazione, <ref-ruling> consid. 2.1 e 2.2, 133 II 249 consid. 1.4). D'altra parte, il Consiglio di Stato ha rilevato che il requisito dell'abilitazione all'insegnamento per esercitare la funzione di docente di sostegno pedagogico è esplicitamente previsto dall'art. 47 in relazione con l'art. 48 cpv. 2 lett. d Lsc. Ora, il ricorrente non censura d'arbitrio l'applicazione di queste disposizioni né postula un controllo accessorio delle stesse. La questione non deve quindi essere ulteriormente approfondita, bastando rilevare che, quand'anche la scelta del legislatore di esigere l'abilitazione all'insegnamento da parte di un candidato in possesso di un titolo accademico in pedagogia possa essere opinabile, non può essere rimproverato al Consiglio di Stato di essere incorso nell'arbitrio per avere annullato la risoluzione municipale ravvisando la mancanza di un requisito per la nomina previsto dalla legge.
4.3 Laddove accenna alle spese processuali ed alle ripetibili poste a suo carico nel giudizio impugnato, il ricorrente si limita ad addurre di essere vittima di una decisione errata ed a rilevare che il ricorso presentato dalla controparte dinanzi al Governo è stato accolto sulla base di motivi da lei non invocati. Egli non censura però l'eventuale applicazione arbitraria degli art. 28 e 31 della legge ticinese di procedura per le cause amministrative, del 19 aprile 1966, che disciplinano questa materia. Né considera la sua soccombenza e l'ammontare comunque ridotto degli importi stabiliti nella decisione impugnata. Sollevata in modo generico, la critica non è sufficientemente motivata e non deve quindi essere ulteriormente esaminata. Il gravame è inoltre parimenti inammissibile laddove il ricorrente accenna al principio della parità di trattamento. Egli non spiega infatti, perlomeno con una motivazione conforme agli art. 42 cpv. 2 e 106 cpv. 2 LTF, in che misura casi simili sono stati trattati in modo diverso senza motivi oggettivi da parte della stessa autorità (cfr. <ref-ruling> consid. 9.1 e rinvii), né invoca le condizioni poste dalla giurisprudenza per ammettere eccezionalmente una parità di trattamento nell'illegalità (cfr. <ref-ruling> consid. 8.6, 127 I 1 consid. 3a e rinvio).
5. 5.1 Il ricorrente lamenta pure una violazione del suo diritto di essere sentito poiché la precedente istanza avrebbe motivato il proprio giudizio sbrigativamente, omettendo di esprimersi su una serie di argomentazioni da lui sollevate nella procedura.
5.2 Il Consiglio di Stato ha annullato la risoluzione municipale essenzialmente per il fatto che il ricorrente difettava dell'abilitazione all'insegnamento, requisito indispensabile per potere essere nominato. Tale motivo è stato esposto nella decisione impugnata. Ritenuto che si tratta dell'unico aspetto rilevante per il giudizio, è senza violare il diritto di essere sentito che la precedente istanza poteva rinunciare a trattare le ulteriori argomentazioni sollevate dalle parti. La decisione impugnata è d'altra parte stata compresa dal ricorrente, che l'ha diffusamente contestata in questa sede, sicché l'obbligo di motivazione dedotto dall'art. 29 cpv. 2 Cost. non è stato disatteso (cfr., al riguardo, <ref-ruling> consid. 4.1 e rinvii).
6. Ne segue che il ricorso in materia di diritto pubblico deve essere respinto in quanto ammissibile, mentre il ricorso sussidiario in materia costituzionale deve essere dichiarato inammissibile. Le spese giudiziarie seguono la soccombenza e sono pertanto poste a carico del ricorrente (art. 66 cpv. 1 LTF), che è parimenti tenuto a rifondere all'opponente, patrocinata da una legale, un'indennità per ripetibili della sede federale (art. 68 cpv. 1 LTF).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso in materia di diritto pubblico è respinto.
2. Il ricorso sussidiario in materia costituzionale è inammissibile.
3. Le spese giudiziarie di fr. 1'000.-- sono poste a carico del ricorrente, che rifonderà all'opponente un'indennità di fr. 2'000.-- a titolo di ripetibili della sede federale.
4. Comunicazione ai patrocinatori delle parti, al Municipio di Chiasso e al Consiglio di Stato del Cantone Ticino.