Faits: A. A.a Y._ SA, qui a pour but l'exploitation d'un commerce de produits laitiers, a engagé X._, avec effet au 1er décembre 2000, en qualité de chauffeur-livreur. Le salaire mensuel de l'employé, perçu treize fois l'an, a été fixé à 4'000 fr., pour une durée hebdomadaire de travail de 47 heures, réparties sur cinq à six jours, et vingt-cinq jours de vacances annuelles. A.b A compter de mars 2002, X._ s'est vu attribuer le camion portant la plaque minéralogique ... et la tournée no .... Cette tournée, qui passait par ..., ..., ..., ..., ..., ..., ... et ..., comptait parmi l'une des plus longues en kilomètres. X._ devait décharger son camion entre neuf et douze fois. Il était aussi tenu d'effectuer certaines livraisons avant des heures déterminées. Ainsi, W._ des ... devait être livrée avant 4h00 et celle de ... avant 7h00. A partir de 2002, X._ a travaillé presque systématiquement six jours sur sept. A.c Par lettre du 29 janvier 2002, Y._ SA a rendu X._ attentif à son devoir de respecter les pauses. En mars 2003, elle lui a adressé un avertissement, en raison de sa lenteur dans le chargement de son camion et de son refus d'obéir aux instructions de son supérieur, d'une part, et d'exécuter le travail demandé, d'autre part. Par lettre du 31 juillet 2003, un nouvel avertissement est parvenu à l'employé; il lui était fait grief de ne pas avoir répondu à la convocation du même jour, d'avoir communiqué le numéro de téléphone direct du chef logistique à plusieurs clients, de ne pas respecter la chaîne du froid et de ne pas faire signer les bulletins de livraison. A.d Du 4 août 2003 au 29 février 2004, X._ a été totalement incapable de travailler, en raison d'une dépression majeure et d'un état d'épuisement. Dès le 19 novembre 2003, la caisse-maladie V._ a versé à l'employeur avec effet rétroactif au 3 septembre 2003 des indemnités journalières à concurrence de 80% du salaire. A.e Le 25 septembre 2003, Y._ SA a résilié le contrat de travail la liant à X._. La résiliation a été réitérée le 14 novembre 2003, avec effet dès le 31 janvier 2004. A.f En mars et avril 2004, ainsi que durant la saison d'hiver 2004-2005, X._ a bénéficié des prestations de l'assurance-chômage. Entre ces deux périodes et de mars à novembre 2005, il a à nouveau travaillé comme salarié pour le compte de tiers. B. Par mémoire-demande du 22 octobre 2003, X._ a ouvert action contre Y._ SA. Dans leur dernier état, ses conclusions visaient à faire condamner la défenderesse au versement de 25'591 fr.65 (fin des rapports de travail), 12'415 fr.80 (heures de nuit), 6'827 fr.16 (heures supplémentaires), 2'841 fr.30 (vacances), 25'000 fr. (tort moral), 24'900 fr. (indemnité pour résiliation abusive), sous déduction des montants versés par la défenderesse après le dépôt de la demande à raison de 33'771 fr.15, le tout avec intérêts à 5% dès le 14 novembre 2003. La demande tendait également à la levée définitive des oppositions faites aux commandements de payer y relatifs, au prononcé d'une réprobation judiciaire et, enfin, à la délivrance d'un certificat de travail au sens de l'art. 330a al. 1 CO. La défenderesse a conclu au rejet de la demande. Statuant le 30 avril 2008, la Cour civile II du Tribunal cantonal valaisan a prononcé que la défenderesse paiera au demandeur 7'110 fr.85, avec intérêts à 5% dès le 1er février 2004, et 5'000 fr., avec intérêts à 5% dès le 14 novembre 2003, que les oppositions formées aux commandements de payer notifiés dans les poursuites nos ... et ... sont définitivement levées, à concurrence de 5'000 fr., avec intérêts à 5% dès le 14 novembre 2003, pour la première, et de 7'110 fr.85, avec intérêts à 5% dès le 1er février 2004, pour la seconde, que la défenderesse délivrera au demandeur un certificat de travail établi dans le sens du considérant 23.2 et que toute autre ou plus ample conclusion est rejetée. Les frais de procédure et de jugement, par 19'900 fr., ont été répartis à raison de 14'925 fr. à la charge du demandeur et de 4'975 fr. à la charge de la défenderesse. Enfin, le demandeur a été condamné à verser à la défenderesse 6'600 fr. à titre de dépens et 4'975 fr. à titre de remboursement d'avances; la défenderesse a été condamnée à verser au demandeur 2'300 fr. à titre de dépens. La motivation du jugement querellé sera détaillée ci-après, dans la mesure utile à l'examen du recours. C. Le demandeur exerce un « recours en matière civile et recours constitutionnel subsidiaire ». A titre principal, il conclut à l'admission du recours en matière civile et à la modification du jugement entrepris, en reprenant les mêmes conclusions que celles formulées devant l'instance cantonale, à l'exception des prétentions en réparation du tort moral qu'il chiffre à 15'000 fr. - et non plus à 25'000 francs. Subsidiairement, il requiert l'admission du recours constitutionnel subsidiaire et l'annulation du jugement entrepris. La défenderesse propose le rejet des deux recours.