Faits: A. Dès le 1er avril 1997, X._ a travaillé en qualité d'acquisiteur professionnel au service externe d'une agence générale de la Compagnie d'Assurances Y._ (ci-après: Y._). L'art. 3.2.1 des conditions d'engagement prévoyait que le collaborateur n'était pas autorisé à transmettre à une autre compagnie d'assurances ou à un courtier, directement ou indirectement, des propositions d'assurance refusées par l'employeur ou les compagnies partenaires, à moins que l'agence ne l'y autorise. Du 1er octobre 2004 au 30 avril 2005, le fils de X._ a travaillé pour A._ Sàrl, en tant qu'acquisiteur en assurances. Après avoir été licencié parce qu'il n'amenait pas assez d'affaires, il a continué à travailler quelques mois comme agent libre pour l'un des associés de son ancienne employeuse. Le 14 mars 2005, Y._ a adressé un avertissement écrit à X._, qui avait imité la signature d'un client sur une proposition d'assurance et contresigné celle-ci en qualité d'agent. Y._ a découvert d'autres cas de propositions d'assurance dont la signature du preneur avait été imitée. Le 5 mars 2008, X._ a été inculpé de faux dans les titres. Courant 2005, le chef de vente vie a interpellé X._, dont il avait constaté qu'il ne produisait pratiquement pas d'assurance vie. Celui-ci a expliqué qu'au vu des commissions versées par Y._, il ne faisait pas les affaire avec elle et les donnait à son fils. X._ a également tenu les mêmes propos en présence de l'agent général et d'un inspecteur d'assurance. Ces déclarations ont circulé au sein du personnel de Y._. Au vu de l'énormité des faits, certains collaborateurs ont pensé à une plaisanterie. Le chef de vente vie a rapporté ces paroles au directeur régional, qui a convoqué X._ pour un entretien le 24 août 2005. A cette occasion, celui-ci a admis avoir aidé son fils qui débutait dans le métier en lui confiant l'opportunité de conclure des contrats d'assurance vie. Le 26 août 2005, Y._ a mis fin au contrat de travail de X._ avec effet immédiat. Sa décision était motivée par l'aveu fait par celui-ci en présence du directeur régional d'avoir sciemment remis plusieurs affaires vie à son fils. Au terme de l'entretien de licenciement, X._ a déclaré qu'il ne se laisserait pas faire et que Y._ ne détenait pas de preuves. B. Le 23 février 2006, X._ a saisi le Juge du district de Sion d'une action tendant à ce que Y._ lui verse la somme de 115'720 fr., finalement ramenée à 78'704 fr., avec intérêt à 5 % dès le 26 août 2005. Par jugement du 18 septembre 2008, la Cour civile II du Tribunal cantonal valaisan a rejeté la demande. En résumé, elle a considéré que Y._ était fondée à licencier X._ avec effet immédiat et que celui-ci ne pouvait dès lors pas faire valoir de prétentions fondées sur l'art. 337c CO. C. X._ (le recourant) interjette un recours en matière civile au Tribunal fédéral. Il conclut à ce que celui-ci annule le jugement du 18 septembre 2008, dise que la résiliation du contrat de travail est "abusive" (sic; recte: injustifiée) et condamne Y._ à lui verser un montant de 78'704 fr. à titre d'indemnisation, avec suite de frais et dépens. Y._ (l'intimée) propose le rejet du recours dans la mesure où il est recevable, sous suite de frais et dépens.