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'<ref-law>.
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.

Considérant en droit:
1. 1.1 Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 et la référence).
Le jugement attaqué a été rendu en matière civile (<ref-law>) par l'autorité judiciaire cantonale de dernière instance (<ref-law>). La valeur litigieuse, qui correspond au montant encore litigieux devant l'autorité précédente (<ref-law>), est de 63'804 fr.76. Partant, la voie du recours en matière civile est ouverte (<ref-law>), si bien que le recours constitutionnel subsidiaire est irrecevable (<ref-law>). Les griefs étant traités sous la forme d'un seul et même recours, sans distinction entre le recours en matière civile et le recours constitutionnel subsidiaire, la question d'une conversion ne se pose pas.
Il convient donc d'entrer en matière sur le recours en matière civile.
1.2 Le recours en matière civile peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (cf. <ref-ruling> consid. 1.4). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (<ref-law>), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent, lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 1.1). Il ne peut pas entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal si le grief n'a pas été invoqué et motivé de manière précise par la partie recourante (<ref-law>).
1.3 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
2. Comme le recourant ne démontre pas, ni même ne soutient, que les juges précédents ont constaté les faits de manière arbitraire, il n'y a pas lieu de tenir compte d'un état de fait qui diverge de celui contenu dans le jugement attaqué.
3. Le recourant scinde les griefs soulevés en deux groupes: il traite d'abord les questions de procédure cantonale, puis celles relatives au droit matériel.
Sous le titre « procédure », il commence par rappeler, d'une manière théorique, les notions de droit d'être entendu, de l'obligation de motiver, d'arbitraire et de formalisme excessif. Il soulève ensuite trois moyens, intitulés « complément de preuve (<ref-law>/<ref-law>) », « Rapport/délibérations/jugement (<ref-law>) » et « frais et dépens ».
Sous le titre « procédure », il commence par rappeler, d'une manière théorique, les notions de droit d'être entendu, de l'obligation de motiver, d'arbitraire et de formalisme excessif. Il soulève ensuite trois moyens, intitulés « complément de preuve (<ref-law>/<ref-law>) », « Rapport/délibérations/jugement (<ref-law>) » et « frais et dépens ».
3.1 3.1.1 Le recourant reproche à la cour cantonale d'avoir rejeté sa requête en preuve portant sur le dépôt de l'arrêt de renvoi du 23 novembre 2007. De son point de vue, les juges valaisans ont considéré, de manière arbitraire, que le délai de « 10 jours après la clôture de l'instruction » prévu à l'<ref-law>/VS n'est pas réalisé. Il argumente en soutenant que le fait nouveau s'est produit quatorze mois après la clôture de l'instruction, que le Tribunal cantonal connaît notoirement l'existence d'une affaire pénale connexe et que cette autorité accuse un retard de plus de douze mois pour appointer le débat final.
La cour cantonale a rejeté la requête en preuve du recourant, en se fondant sur l'<ref-law>/VS, selon lequel après le débat préliminaire, les parties ne peuvent plus faire valoir de nouveaux moyens de preuve (al. 1). Elle a ensuite relevé que l'<ref-law>/VS, invoqué par le recourant, ne lui est d'aucun secours, puisqu'il concerne l'allégation de faits nouveaux et non pas l'administration d'un nouveau moyen de preuve; elle a ajouté que même s'il fallait admettre une application analogique de cette disposition en matière de preuve, les conditions posées par l'<ref-law>/VS ne seraient pas réalisées, la requête du recourant intervenant plus de dix jours après la clôture de l'instruction. Elle a enfin relevé que le moyen de preuve requis n'était pas propre à établir un fait introduit en cause.
Dans la mesure où le recourant axe l'entier de sa critique sur la violation du délai de dix jours de l'<ref-law>/VS, qui ne constitue qu'un élément subsidiaire du raisonnement des juges cantonaux, sa critique est d'emblée dénuée de fondement.
3.1.2 Dans le même grief, le recourant affirme que la cour cantonale in extenso ne disposait pas de la « compétence matérielle à refuser le complément d'instruction », puisque seul le Président pouvait statuer. A titre de motivation, il invoque le « renvoi de l'<ref-law>/VS ». Selon cette disposition, lorsque l'<ref-law>/VS doit être appliqué devant le Tribunal cantonal, le complément d'instruction est effectué: a) par le juge cantonal statuant comme juge unique; b) par un juge délégué lorsque la cause relève d'une cour. L'<ref-law>/VS traite du pouvoir du « juge » de faire administrer d'office, même au débat final, des preuves qui n'ont pas été proposées par les parties.
Dès lors que le recourant n'explique pas en quoi l'autorité cantonale aurait fait une application arbitraire, ou contraire à un autre droit constitutionnel, de l'<ref-law>/VS, voire de l'<ref-law>/VS, la critique est vaine. On ne voit du reste pas comment le recourant déduit du « renvoi de l'<ref-law>/VS » la compétence du seul Président du Tribunal cantonal pour statuer sur le refus d'un complément d'instruction.
3.2 Après avoir reproduit le contenu des art. 13 al. 9 de la Loi d'organisation judiciaire du 27 juin 2000 (LOJ/VS), 9 al. 4 du Règlement d'organisation des tribunaux valaisans du 4 mai 1999 (ROTVS) et 209 al. 1, 211 al. 1 et 213 al. 1 CPC/VS, le recourant relève que le débat final a eu lieu le 25 octobre 2007 à 10h30 et que le jugement attaqué est daté du 30 avril 2008, soit 188 jours après le débat final. Il prétend ensuite que le rapport écrit prévu à l'art. 9 ROTVS n'a vraisemblablement pas été établi dans le délai imparti et ajoute que le délai de l'<ref-law>/VS n'a pas non plus été respecté. Il souligne encore l'absence d'indication dans le jugement entrepris du nom du greffier ayant participé au débat final. Fort de ces explications, le recourant conclut que le jugement attaqué est matériellement affecté de vices procéduraux incompatibles avec le texte de l'<ref-law>/VS et des art. 13 al. 9 LOJ/VS, 9 al. 4 et 5 ROTVS.
Le recourant ne dénonce pas une application arbitraire, ou contraire à un autre droit constitutionnel, du droit de procédure cantonal invoqué. En cela, la critique est irrecevable. Rien ne semble du reste indiquer que l'autorité cantonale aurait fait une application insoutenable des dispositions dénoncées.
3.3 Le recourant conteste enfin la répartition des frais opérée par l'autorité cantonale. Il soutient qu'en mettant les frais par 75% à sa charge, l'autorité cantonale a arbitrairement appliqué l'<ref-law>/VS.
3.3.1 Selon l'<ref-law>/VS, les frais sont, en règle générale, mis à la charge de la partie qui succombe. Lorsqu'aucune des parties n'a entièrement gain de cause, ils sont répartis proportionnellement entre elles (al. 1). Il ressort clairement de cette disposition que le législateur cantonal a laissé au juge un très large pouvoir d'appréciation dans la répartition des frais. En particulier, il ne lui est en aucun cas imposé de répartir ceux-ci dans une proportion qui corresponde mathématiquement à la différence entre les conclusions et les montants finalement alloués (cf. arrêt 5P.384/2002 du 17 décembre 2002).
3.3.2 Pour justifier la répartition des frais et dépens à raison de trois quarts à la charge du recourant et d'un quart à celle de l'intimée, l'autorité cantonale a indiqué que sur les 63'804 fr.76 réclamés, le recourant a obtenu 12'110 fr.85 (7'110 fr.85 + 5'000 fr.). Elle a ajouté que la prétention tendant à l'établissement d'un nouveau certificat de travail a en outre été admise et que ce n'est qu'en cours de procédure que l'intimée a indemnisé le recourant pour ses heures supplémentaires.
A l'appui de son grief, le recourant allègue que la partie adverse lui a payé, après le dépôt de la demande, 33'771 fr.15, référence faite aux « allégués 2.116, 117, 123, 133, 138 ». Ce montant aurait dû être ajouté aux 12'110 fr.85 encore dus pour dire dans quelle mesure il a obtenu gain de cause. Les allégués cités, à supposer qu'il s'agisse de ceux du mémoire-conclusions, concernent le paiement des salaires de septembre 2003 (3'191 fr.70), octobre et novembre 2003 (6'523 fr.55), décembre 2003 (7'699 fr.90), janvier 2004 (3'320) et février 2004 (3'419 fr.70), pour un total de 24'154 fr.85 - et non pas de 33'771 fr.15.
Il sied tout d'abord de relever que le seul renvoi aux « allégués 2.116, 117, 123, 133, 138 », s'agissant des montants payés en cours de procédure, sans autre précision, paraît insuffisant pour démontrer une application arbitraire par l'autorité cantonale de l'<ref-law>/VS. Peu importe en définitive, puisque le grief ne peut qu'être écarté.
L'autorité cantonale a retenu que l'intimée a versé 36'951 fr.15: soit 4'265 fr. bruts pour le mois d'août, 4'265 fr. bruts pour le mois de septembre, 7'189 fr.80 bruts pour les mois d'octobre et novembre, 7'405 fr. en décembre 2003, comprenant 3'970 fr. nets à titre de 13ème salaire, et 13'826 fr.35 bruts en janvier 2004, comprenant 3'320 fr. nets de salaire, 10'114 fr.80 nets d'heures supplémentaires et de vacances et 276 fr.55 nets à titre de 13ème salaire.
Il ne ressort pas du jugement que les salaires échus avant le dépôt de la demande, le 22 octobre 2003, ont été acquittés postérieurement à celui-ci. Leur paiement ne saurait donc être pris en compte, en faveur du recourant, dans le calcul de la répartition des frais. Il en va de même des créances en salaire des mois d'octobre, novembre, décembre 2003 et janvier 2004, puisque leur paiement ne constitue pas une reconnaissance par l'intimée du bien-fondé des prétentions du recourant. Comme ces montants arrivaient à échéance en cours d'instance, ils n'avaient pas à être exécutés antérieurement à l'ouverture de l'action; en s'acquittant des montants en question, l'intimée n'a fait que se conformer à ses obligations contractuelles. Le montant versé en janvier 2004 au titre des vacances ne saurait de même entrer en ligne de compte dans la répartition des frais, dès lors que le recourant n'a pas obtenu gain de cause sur ce point: il a été retenu que, sur l'ensemble de la relation contractuelle, l'employé avait pris 4,84 jours de vacances en trop et était à ce titre redevable de 1004 fr.80 envers l'intimée. Quant au paiement des heures supplémentaires allouées au recourant, il est intervenu en janvier 2004, soit en cours d'instance et alors que le recourant se trouvait en congé maladie; la créance a vraisemblablement été acquittée en raison de la procédure judiciaire. Les juges cantonaux, qui ont mentionné dans la motivation relative à la répartition des frais que « ce n'est qu'en cours de procédure que la défenderesse a indemnisé le demandeur de ses heures supplémentaires », ont tenu compte de ce facteur.
Les heures supplémentaires admises représentent 6'286 fr.90. Si on ajoute ce chiffre aux 12'110 fr.85 alloués au recourant, on obtient 18'397 fr.75, soit environ 29% des prétentions totales (63'804 fr.76). Compte tenu du large pouvoir d'appréciation de la cour cantonale, celle-ci pouvait admettre, sans sombrer dans l'arbitraire, que les trois quarts des frais devaient être supportés par le recourant.
4. L'autorité cantonale a jugé que le licenciement de l'employé était abusif au sens des art. 336 al. 1 let. a et d CO et qu'une indemnité de 12'450 fr., correspondant à trois mois de salaire, était appropriée.
Selon le recourant, la cour cantonale a violé le pouvoir d'appréciation à elle conféré par l'<ref-law> (recte: 336a al. 2 CO), en refusant de lui allouer six mois de salaire à titre d'indemnité pour licenciement abusif. Le recourant affirme que la cour cantonale a omis, dans son appréciation, de peser à leur juste valeur les critères de faute grave, de situation de monopole de l'employeur et de gravité de l'atteinte à la personnalité du travailleur. Le recourant ajoute que l'allocation de trois mois de salaire, à titre d'indemnité, est contradictoire avec le principe de l'allocation pour tort moral.
4.1 La partie qui résilie abusivement le contrat doit verser à l'autre une indemnité (<ref-law>).
Le juge fixe l'indemnité en équité en fonction de toutes les circonstances (<ref-law>; <ref-ruling> consid. 5.2; <ref-ruling> consid. 3c); il doit notamment tenir compte de la gravité de la faute de l'employeur, d'une éventuelle faute concomitante du travailleur, de la manière dont s'est déroulée la résiliation, de la gravité de l'atteinte à la personnalité du travailleur licencié, de la durée des rapports de travail, de leur étroitesse, des effets économiques du licenciement, de l'âge du travailleur, d'éventuelles difficultés de réinsertion dans la vie économique et de la situation économique des parties (ATF <ref-ruling> consid. 3 et les arrêts cités; arrêt 4C.177/2003 du 21 octobre 2003, consid. 3.5; 4C.86/2001 du 28 mars 2002, consid. 1a; 4C.310/1998 du 8 janvier 1999, reproduit in: SJ 1999 I 277, consid. 3c).
Le montant de l'indemnité est fixé librement par le juge; le pouvoir d'appréciation qui est reconnu de la sorte à l'autorité cantonale conduit le Tribunal fédéral à ne pas substituer sa propre appréciation à celle de l'instance inférieure. Il intervient lorsque la décision s'écarte sans raison des règles établies par la doctrine et la jurisprudence en matière de libre appréciation, ou lorsqu'elle s'appuie sur des faits qui, dans le cas particulier, ne devaient jouer aucun rôle, ou encore lorsqu'elle ignore des éléments qui auraient absolument dû être pris en considération; en outre, le Tribunal fédéral redresse les décisions rendues en vertu d'un pouvoir d'appréciation lorsqu'elles aboutissent à un résultat manifestement injuste ou à une iniquité choquante (<ref-ruling> consid. 3.1, 28 consid. 4.1; <ref-ruling> consid. 2).
Le montant de l'indemnité est fixé librement par le juge; le pouvoir d'appréciation qui est reconnu de la sorte à l'autorité cantonale conduit le Tribunal fédéral à ne pas substituer sa propre appréciation à celle de l'instance inférieure. Il intervient lorsque la décision s'écarte sans raison des règles établies par la doctrine et la jurisprudence en matière de libre appréciation, ou lorsqu'elle s'appuie sur des faits qui, dans le cas particulier, ne devaient jouer aucun rôle, ou encore lorsqu'elle ignore des éléments qui auraient absolument dû être pris en considération; en outre, le Tribunal fédéral redresse les décisions rendues en vertu d'un pouvoir d'appréciation lorsqu'elles aboutissent à un résultat manifestement injuste ou à une iniquité choquante (<ref-ruling> consid. 3.1, 28 consid. 4.1; <ref-ruling> consid. 2).
4.2 4.2.1 Il convient tout d'abord d'observer que l'allocation correspondant à trois mois de salaire n'est pas incompatible avec le principe de l'allocation du tort moral. En effet, la jurisprudence a admis le versement d'une indemnité pour tort moral en application de l'<ref-law> indépendamment de l'indemnité prévue à l'<ref-law>, lorsque le préjudice subi ne résulte pas de la cause liée au caractère abusif du congé (arrêt 4C.84/2005 du 16 juin 2005, consid. 5.1; arrêt 4C.310/1998 du 8 janvier 1999, reproduit in: SJ 1999 I 277, consid. 4c; cf. également ATF <ref-ruling> consid. 3c; arrêt 4C.177/2003 du 21 octobre 2003, consid. 4.1). Or, tel est précisément le cas en l'espèce: l'atteinte à la personnalité du recourant retenue par la cour cantonale pour justifier l'indemnité pour tort moral découle de la violation par l'employeur de son devoir fondé sur l'<ref-law> en astreignant le recourant à des conditions de travail inacceptables qui ont influé sur sa santé, alors que l'employé a été congédié en raison de sa personnalité qui ne convenait pas à ses supérieurs et des différentes prétentions formulées par son avocat. La cour cantonale pouvait donc allouer une réparation morale sur la base de l'<ref-law>, sans qu'il ne soit nécessaire que l'atteinte ait une gravité telle que sa réparation dépasse le versement de l'indemnité maximale de l'<ref-law>.
4.2.2 Pour fixer l'indemnité allouée au recourant, l'autorité cantonale s'est référée aux circonstances du cas d'espèce, en soulignant que le contrat a été résilié parce que A._ et B._ n'appréciaient pas l'employé et après que celui-ci a fait valoir des prétentions à l'endroit de son employeur, que les rapports de travail n'ont duré que trois ans, que les pressions subies par l'employé n'ont eu lieu que durant les derniers mois, qu'au moment du licenciement, l'employé était âgé de 57 ans et n'avait pas de charge de famille et qu'enfin, après seulement deux mois de chômage, il a retrouvé un emploi.
Quoi qu'en dise le recourant, l'autorité cantonale n'a pas omis de prendre en considération certains faits à même de justifier l'octroi d'une indemnité supérieure à celle octroyée. Elle n'avait notamment pas à tenir compte de l'atteinte consécutive au comportement de l'employeur contraire à l'<ref-law>, dans la mesure où cette atteinte ne résulte pas du caractère abusif du congé. Il en va de même de la situation de monopole de l'employeur invoquée par le recourant, à supposer qu'elle soit établie. Cet élément est dénué de pertinence, dès lors que le recourant a retrouvé un emploi, après deux mois de chômage, et que ce fait a été dûment pris en compte. Enfin, même si la cour a considéré à tort les pressions subies par l'employé, puisqu'elles sont antérieures au congé, son appréciation n'aboutit pas à un résultat manifestement injuste ou à une iniquité choquante, ce qui n'est en aucun cas démontré par le recourant. Cela étant, la cour cantonale n'a pas abusé du large pouvoir d'appréciation dont elle jouit, en ayant considéré que les circonstances de l'espèce justifiaient une indemnité correspondant à trois mois de salaire.
Le grief se révèle infondé.
5. L'autorité cantonale a jugé qu'en sus de l'indemnité prévue à l'<ref-law> une indemnité pour tort moral de 5'000 fr. était justifiée sur la base de l'<ref-law>.
5.1 La fixation de l'indemnité pour tort moral est une question d'application du droit fédéral, que le Tribunal fédéral examine librement. Dans la mesure où celle-ci relève pour une part importante de l'appréciation des circonstances, le Tribunal fédéral intervient avec retenue, notamment si l'autorité cantonale a mésusé de son pouvoir d'appréciation en se fondant sur des considérations étrangères à la disposition applicable, en omettant de tenir compte d'éléments pertinents ou encore en fixant une indemnité inéquitable parce que manifestement trop faible ou trop élevée (<ref-ruling> consid. 5.1 et les arrêts cités).
5.2 Le recourant critique la quotité de l'indemnité allouée. Il prétend que les magistrats valaisans ont omis de prendre en considération un certain nombre d'éléments, comme le mobbing caractérisé dont il a été victime, le traitement discriminatoire et vexant qu'il a subi, le fait d'avoir été considéré comme un malade imaginaire et le non-paiement de son salaire du 4 août au 25 novembre 2003; il invoque aussi les périodes de chômage, la pénible convalescence consécutive au choc psychologique subi à 57 ans passés, le stress des heures supplémentaires hebdomadaires sans rémunération et la dépression subie.
Dans le présent grief - comme dans le précédent -, le recourant perd de vue que l'autorité est libre de fixer, en équité, le montant de l'indemnité. Il ne cherche ainsi nullement à démontrer que le raisonnement de la cour aboutirait à un résultat inéquitable. En réalité, le recourant substitue, de manière purement appellatoire, sa propre appréciation à celle du Tribunal cantonal, en reprenant les mêmes éléments d'appréciation que la cour cantonale, à l'exception du non-paiement du salaire et des périodes de chômage, qui ne lui sont d'aucun secours. Le non-paiement du salaire d'août à novembre 2003 est invoqué par le recourant en tant que facteur d'aggravation de sa dépression; or, le Tribunal cantonal n'a pas omis de prendre en compte la dépression sévère du recourant. Quant aux périodes de chômage, elles ne sont pas liées aux conditions de travail inacceptables subies par le recourant; par ailleurs, elles ne sauraient, à elles seules, rendre manifestement trop faible l'indemnité octroyée. Enfin, cette indemnité n'apparaît pas inéquitable, au regard des éléments sur lesquels la cour a pris appui, à savoir les circonstances dans lesquelles le recourant a été contraint d'accomplir des heures supplémentaires, les quelque neuf heures supplémentaires par semaine, l'absence de compensation et de rémunération de ces heures durant la relation contractuelle, l'inégalité de traitement subie par rapport aux autres chauffeurs, la non-prise en compte des plaintes formulées par l'employé, la mise en doute de la réalité de ses souffrances psychiques, la dépression sévère et l'épuisement professionnel de l'employé, son incapacité totale de travail durant près de six mois et le traitement suivi pendant plus d'une année, mais, encore, l'absence de séquelles.
Pour autant qu'il soit recevable, le grief est mal fondé.
6. Le recourant reproche à l'autorité cantonale de n'avoir pas prononcé une réprobation judiciaire.
Selon l'<ref-law>, le juge peut substituer ou ajouter à l'allocation d'une indemnité en réparation du tort moral un autre mode de réparation. Cette disposition laisse au juge une grande liberté dans la détermination du mode de réparation. Considérant que la reconnaissance explicite des droits du recourant et l'allocation d'une indemnité pour tort moral constituaient déjà une réparation adéquate de l'atteinte à son honneur professionnel, l'autorité cantonale a jugé qu'il n'y avait pas lieu de prononcer une réprobation judiciaire.
A lire le recourant, la réprobation judiciaire demandée devait être octroyée, sur le vu du contexte local des emplois de chauffeur et de l'existence d'une procédure pénale pour faux témoignage et d'une autre procédure liée au conflit de travail. Le recourant n'explique pas en quoi le refus de prononcer une réprobation judiciaire serait inéquitable. On cherche par ailleurs en vain quelle pourrait être la portée des arguments avancés à l'appui de son raisonnement. Une fois encore, le grief tombe à faux.
7. Le dernier moyen soulevé se rapporte au travail de nuit.
Il n'est pas contesté que le recourant a régulièrement effectué un travail de nuit. Les prétentions financières soulevées à ce titre concernent la période antérieure au 1er août 2003.
L'autorité cantonale a arrêté que l'art. 17b LTr, qui prévoit une indemnisation en cas de travail de nuit, n'est pas applicable, dans la mesure où il est entré en vigueur pour les hommes le 1er août 2003. L'ancien droit - l'art. 16 al. 2 aLTr - ne prévoyant aucune compensation en repos ou en salaire pour les travailleurs appelés à travailler régulièrement la nuit, la prétention du recourant y relative a été rejetée.
Le recourant y voit une violation de l'art. 17b LTr et de l'art. 16 al. 2 aLTr et, par voie de conséquence, de l'<ref-law>, le calcul du salaire afférent aux vacances étant modifié par la rémunération obtenue pour le travail de nuit. Il soutient que la faible rémunération convenue à titre de salaire ne pouvait manifestement inclure les indemnités à verser pour le travail de nuit. Par son argumentation, le recourant détourne le raisonnement de l'autorité cantonale, qui a non pas retenu que le salaire convenu incluait les indemnités à verser, mais qui a, au regard des dispositions applicables en la matière, jugé que le recourant n'avait pas droit à être rémunéré pour les heures effectuées durant la nuit. L'argumentation du recourant, qui fait totalement fi du raisonnement suivi par les juges cantonaux, est déficiente et ne peut que conduire à l'irrecevabilité du moyen soulevé.
8. Par conséquent, le recours en matière civile est rejeté dans la mesure de sa recevabilité.
9. Compte tenu de l'issue du litige, les frais judiciaires et dépens sont mis à la charge du recourant, qui succombe (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière civile est rejeté dans la mesure de sa recevabilité.
2. Le recours constitutionnel subsidiaire est irrecevable.
3. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
4. Une indemnité de 3'500 fr., à payer à l'intimée à titre de dépens, est mise à la charge du recourant.
5. Le présent arrêt est communiqué aux mandataires des parties et à la Cour civile II du Tribunal cantonal du canton du Valais.
Lausanne, le 12 septembre 2008
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
Le Président: La Greffière:
Corboz Crittin