Faits: A. A.a Le 25 octobre 2004, la société X._ a engagé Y._, en qualité de collaboratrice au bureau commercial. A la suite d'un vol d'argent commis sans effraction dans un des bureaux de la société, plusieurs employés de X._ ont été entendus par la police. Y._ l'a été aux fins de renseignements le 9 mai 2006. Le 31 du même mois, une circulaire interne annonçait que l'enquête de police avait permis d'identifier l'auteur du vol: il s'agissait d'un inspecteur de régulation, qui avait agi seul et sans complicité au sein de la compagnie. A.b Le 14 juillet 2006, le contrat de travail liant les parties a été résilié avec effet le 31 octobre 2006, « en raison d'une irrémédiable rupture de confiance ». Le 15 juillet 2006, Y._ s'est opposée à son congé. B. Le 8 août 2006, Y._ a assigné X._ devant le Tribunal des prud'hommes du district de Neuchâtel. Après avoir modifié ses conclusions, la demanderesse concluait au paiement de 1'941 fr. avec intérêts à 5% l'an dès le 17 août 2006, à titre de dommage résultant de la fin prématurée de ses cours de formation et de 27'728 fr.40 avec intérêts à 5% l'an dès le 10 août 2006, à titre d'indemnité pour résiliation abusive, correspondant à six mois de salaire brut, y compris la part au treizième salaire. La défenderesse a conclu au rejet de la demande, sous suite de dépens. Par jugement du 21 mai 2007, le Tribunal des prud'hommes a condamné la défenderesse à verser à la demanderesse le montant de 18'480 fr. nets à titre d'indemnité pour licenciement abusif; cette indemnité correspondait à quatre mois de salaire. Statuant le 5 août 2008 sur recours de la défenderesse, la Cour de cassation civile du Tribunal cantonal neuchâtelois a rejeté le recours. La cour cantonale a considéré que les premiers juges ont retenu avec raison l'application de l'art. 336 CO; pour les magistrats cantonaux, le licenciement était bien abusif au sens de cette disposition, dès lors qu'il apparaissait comme une mesure de représailles, signifiée suite aux hypothèses formulées par l'employée alors qu'elle était interrogée par la police et devait répondre à des questions précises. C. La défenderesse exerce un recours en matière civile au Tribunal fédéral. Elle conclut à l'annulation de l'arrêt entrepris et au renvoi de la cause aux instances inférieures pour nouveau jugement. La demanderesse propose le rejet du recours. 