Faits:
A. A.a En août 1998, X._, courtier indépendant en assurances, a engagé Y._, en qualité de secrétaire à mi-temps. Celle-ci collaborait avec deux autres secrétaires, A._, qui travaillait un jour et demi par semaine, et B._, occupée à 100%, puis à 90 et 80%.
A.b Les employés étaient parfois amenés à effectuer des heures supplémentaires en raison d'une surcharge de travail et de remplacement en cas d'absence. A._ et B._ notaient leurs heures supplémentaires et soumettaient régulièrement leur décompte à X._, qui les compensait en congé. Quant à Y._, toute compensation des heures supplémentaires, occasionnellement évoquées, lui a été refusée, au motif qu'elle bénéficiait d'autres avantages, liés à la relation amoureuse qu'elle entretenait avec l'employeur.
Cette relation a pris fin en août 2004. Depuis lors, les rapports professionnels sont devenus tendus.
A.c A la fin septembre 2004, Y._ a réclamé à son employeur le paiement des heures supplémentaires effectuées et des jours de vacances non pris en 2004.
A partir du 5 octobre 2004, l'employée a été en incapacité totale de travailler. Le 26 novembre 2004, elle a donné son congé pour le 30 du même mois, ce qui a été accepté par l'employeur.
A.d Le 9 décembre 2004, Y._ a fait notifier à X._ - qui s'y est opposé - un commandement de payer pour les montants de 28'500 fr., avec intérêts à 5% dès le 20 octobre 2004, à titre de créances de salaire, et de 42'536 fr.20, avec intérêts à 5% dès le 1er décembre 2004, pour le remboursement de prétendus prêts.
B. B.a Le 28 avril 2005, Y._ a assigné X._ en paiement de la somme de 30'000 fr., avec intérêts à 5% dès le 1er décembre 2004, et requis jusqu'à due concurrence la mainlevée définitive de l'opposition faite au commandement de payer. La demanderesse a par la suite précisé le montant de ses prétentions, en indiquant qu'il s'agissait de 30'000 fr. bruts.
Par jugement du 30 mai 2006, le Tribunal du travail du canton du Valais a rejeté la demande. Après avoir reconnu que la demanderesse avait effectué un total de 75 jours de travail supplémentaire, le tribunal a considéré que, compte tenu des liens affectifs qui unissaient les parties, la demanderesse avait bénéficié de conditions de travail particulières qui compensaient les heures supplémentaires accomplies. Il a donc été jugé que la créance de la demanderesse était éteinte par compensation.
B.b La demanderesse a interjeté appel contre ce jugement, en concluant à l'annulation du jugement entrepris, puis en reprenant les mêmes conclusions que celles formulées devant le Tribunal du travail.
Statuant le 8 octobre 2007, la Cour civile II du Tribunal cantonal valaisan a prononcé que le défendeur paiera à la demanderesse le montant net de 23'002 fr.30, avec intérêts à 5% dès le 1er décembre 2004, et que le défendeur prélèvera les charges sociales sur le montant brut de 25'291 fr.15 et les versera aux caisses sociales afférentes. L'opposition formée au commandement de payer a été définitivement levée à due concurrence.
Les magistrats ont fixé le nombre de jours de travail supplémentaire effectués par la demanderesse à 124.5 (166.5 - 42), après avoir jugé que les données de l'agenda électronique étaient suffisamment fiables pour être prises en compte dans le calcul des jours supplémentaires. Ils ont nié l'existence de tout accord, même oral, dérogeant à l'<ref-law>, lequel aurait permis au défendeur de déroger au principe de la rétribution majorée des heures supplémentaires.
C. Contre ce prononcé, le défendeur exerce un recours de droit civil au Tribunal fédéral. Il requiert l'annulation du jugement du 8 octobre 2007 et le rejet des prétentions de la demanderesse.
La demanderesse propose le rejet du recours. Quant à l'autorité cantonale, elle se réfère aux considérants de son jugement.

Considérant en droit:
1. 1.1 Interjeté par la partie qui a succombé dans ses conclusions (<ref-law>) et dirigé contre un jugement final (<ref-law>) rendu en matière civile (<ref-law>) par une autorité cantonale de dernière instance (<ref-law>) dans une affaire pécuniaire concernant le droit du travail dont la valeur litigieuse atteint le seuil de 15'000 francs (<ref-law>), le recours en matière civile est en principe recevable, puisqu'il a été déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi.
1.2 Le recours 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. 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>).
2. Le recourant fait grief à l'autorité cantonale d'avoir interprété le résultat de l'administration des preuves de manière arbitraire et d'avoir ainsi porté foi aux données de l'agenda électronique pour décompter les jours de travail supplémentaire.
2.1 A teneur de l'<ref-law>, le Tribunal fédéral peut rectifier ou compléter d'office les constatations de l'autorité précédente si les faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law>. Ce n'est que dans cette mesure que la partie recourante est recevable à critiquer les constatations de fait, et cela uniquement pour autant que la correction du vice soit susceptible d'influer sur le sort de la cause (<ref-law>).
La notion de « manifestement inexacte » correspond à celle d'arbitraire au sens de l'art. 9 Cst. Il convient de rappeler que le juge dispose d'un large pouvoir lorsqu'il apprécie les preuves. La partie recourante doit ainsi démontrer dans quelle mesure le juge a abusé de son pouvoir d'appréciation et, plus particulièrement, qu'il a omis, sans aucune raison sérieuse, de prendre en compte un élément de preuve propre à modifier la décision attaquée, qu'il s'est manifestement trompé sur son sens et sa portée ou encore qu'il a, en se fondant sur les éléments recueillis, tiré des constatations insoutenables (<ref-ruling> consid. 2.1).
2.2 La cour cantonale, après avoir décidé de ne pas se fonder sur le décompte manuscrit de l'intimée en indiquant clairement que tout porte à croire qu'en réalité l'employée a confectionné de toute pièce le décompte en lui donnant l'apparence d'un brouillon tenu négligemment pour appuyer ses revendications, s'est penchée sur la force probante d'un autre moyen de preuve produit, à savoir les données imprimées de l'agenda électronique de l'entreprise.
Elle a tout d'abord relevé, relativement à ce moyen de preuve, qu'il n'y avait aucun élément au dossier, qui permettait de soupçonner que les données imprimées auraient été enregistrées ou modifiées ultérieurement. A cet égard, elle a énuméré tout un ensemble d'éléments, qui plaident en faveur de l'authenticité de ce document. Parmi ces éléments figurent la probité dont a fait montre l'intimée dans ses revendications, la formulation variée des indications portées à l'agenda, qui atteste qu'elles ont été écrites spontanément à des moments différents, le défaut de concordance entre les informations de l'agenda, le décompte manuscrit et les allégués de la demande, l'attitude adoptée par l'intimée qui a sollicité l'administration d'une expertise dans le but d'établir que les jours supplémentaires n'avaient pas été portés à l'agenda après le mois d'août 2004, le fait que l'agenda électronique puisse être consulté en réseau. La cour a également estimé que le Tribunal du travail a considéré à tort que l'intimée devait supporter une part de responsabilité pour n'avoir pas présenté de décompte à son employeur, puisqu'il a été retenu que l'employeur a toujours refusé toute entrée en matière lorsque l'intimée abordait la question de la compensation des heures supplémentaires. Selon la cour cantonale, le comportement de l'employeur à l'égard de l'employée expliquait le fait qu'elle ne lui ait pas présenté de décompte détaillé. La cour a encore considéré, après avoir comparé les jours supplémentaires notés dans l'agenda électronique par l'intimée avec ceux effectués par B._ en 2004, que le nombre de jours de travail supplémentaire tels que ressortant de l'agenda paraissait crédible. Elle a enfin relevé que l'engagement d'une secrétaire à 100%, à la suite du départ de l'intimée, confirmait que la surcharge de travail était très importante.
Sur la base de ces éléments d'appréciation, la juridiction cantonale a décidé qu'elle pouvait se fonder sur l'agenda électronique pour décompter les jours de travail supplémentaire et a arrêté leur nombre à 124.5, obtenu en déduisant les 42 jours de vacances pris en trop des 166.5 jours supplémentaires agendés.
2.3 Le recourant estime tout d'abord que le comportement « déloyal », adopté par l'intimée en cours de procédure en lien avec le décompte manuscrit, enlève toute crédibilité aux données imprimées de l'agenda électronique, dont il est permis de penser qu'elles ont été enregistrées ou modifiées. Si l'argument peut paraître percutant, il n'est toutefois pas décisif, car, comme relevé précisément par la cour, un certain nombre d'indices viennent corroborer la thèse contraire.
Le recourant revient sur la majorité des éléments qui ont fondé l'appréciation de l'autorité cantonale. La cour a indiqué, en faveur de l'intimée, que celle-ci avait imputé les jours de vacances pris en trop dans le calcul de ses prétentions. Elle en a déduit que l'intimée n'a pas uniquement invoqué les données informatiques à son avantage. En dépit de ce que soutient le recourant, cette considération est indépendante du fait que l'intimée ait réclamé un nombre de jours de travail supplémentaire supérieur à celui figurant dans l'agenda. On ne saurait par ailleurs en déduire que l'employée a triché sur les jours marqués dans l'agenda. Sur ce point, la démonstration du recourant est vaine.
La cour cantonale a également invoqué la probité de l'intimée, s'agissant de ses revendications tant sous l'angle des jours, ou des heures, supplémentaires réclamés que sous l'angle du remboursement des prêts accordés à l'employeur, faisant l'objet d'une procédure séparée. Le recourant tente de combattre ces arguments, qu'il nomme « troisième » et « quatrième motif », en discutant ce que l'intimée a obtenu à la suite de ses revendications. Ainsi, il met en cause l'argument selon lequel les heures supplémentaires ont été réclamées depuis 2004 seulement, en affirmant qu'il est contradictoire d'en déduire quoi que ce soit, puisqu'il a été jugé que l'intimée n'a pas établi avoir effectué les heures supplémentaires alléguées. De même, il conteste l'argument selon lequel l'intimée a su distinguer les prêts, dont elle a réclamé le remboursement, des cadeaux parfois onéreux dont elle a gratifié son amant, en soulignant qu'elle n'a obtenu en définitive que 11'000 fr. sur les 45'000 fr. réclamés. Dans la mesure où la critique ne touche pas les arguments pris en compte par la cour, elle est sans consistance.
La cour a retenu, comme indice supplémentaire plaidant en faveur de l'authenticité de l'agenda électronique, la non-crainte, de la part de l'intimée, du résultat de l'expertise qu'elle a elle-même proposée spontanément et qui tendait à déterminer le moment précis où les heures supplémentaires ont été portées dans l'agenda. Si la cour tire argument de l'attitude adoptée par l'intimée face à la perspective d'une éventuelle expertise, le recourant discute le caractère pertinent de l'administration d'une telle expertise, référence faite à une attestation produite en annexe à la détermination sur appel. A nouveau, le moyen ne se rapporte pas à l'argument de la cour et ne saurait donc être valablement pris en considération. Ce résultat s'impose d'autant plus que l'expertise dont il est question n'a pas été administrée, motif pris que les éléments figurant au dossier étaient suffisants pour statuer sur la prétention de l'intimée et que, sur ce point, le recourant ne fait état d'aucune violation du droit de procédure cantonal.
La cour cantonale a encore relevé que la possibilité offerte à tout le personnel du bureau d'assurances de pouvoir consulter en réseau l'agenda électronique donnait une force probante accrue à ce document. Le recourant ne revient pas sur ce point, mais débat du contenu de l'agenda, en mettant en exergue le fait que l'intimée était la seule employée qui indiquait ses présences au bureau. Par ailleurs, dans la mesure où le recourant ne conteste pas la signification donnée par la cour aux indications, telles que « P. journée », « P. », « P. bureau », portées par l'intimée sur cet agenda, on ne voit pas en quoi son argumentation est pertinente. On ne saurait enfin tiré argument du fait que toutes les secrétaires, à l'exception de l'intimée, établissaient très régulièrement un décompte des heures supplémentaires, dès lors qu'il a été retenu que l'intimée bénéficiait d'un régime différent des autres employées et que toute entrée en matière sur les heures supplémentaires lui avait été refusée.
La cour a mentionné que, dès lors que le recourant avait renoncé à contrôler lui-même les horaires des secrétaires et qu'il se fiait au décompte manuscrit qu'elles lui présentaient, il est mal venu de reprocher à l'intimée de ne pas pouvoir prouver autrement - que par un décompte manuscrit - l'ampleur de ses heures supplémentaires. Selon le recourant, l'argument est incompréhensible, dans la mesure où, précisément, l'intimée n'a pas tenu de décompte manuel immédiat, comme les autres employées. Force est d'admettre, avec le recourant, que la formulation utilisée par la cour n'est pas très heureuse. Toutefois, dès lors que, dans le but de justifier la valeur probante de l'agenda électronique, la cour explique, de façon précise, en prolongement du développement qui précède, pour quelle raison l'intimée était légitimée à ne pas établir un décompte manuscrit, la critique est dénuée de toute pertinence.
Le recourant prétend que l'intimée aurait clairement compris que, du point de vue de l'employeur, elle n'avait aucune prétention à faire valoir, ce qui explique l'absence de décompte de sa part. En persévérant au cours des années dans le mécanisme mis en place, l'intimée aurait conforté l'employeur dans l'idée qu'elle partageait son point de vue. Le raisonnement du recourant prend appui sur des faits qui n'ont pas été retenus par la cour cantonale, tout en faisant fi des revendications répétées formulées par l'intimée au sujet des jours de travail supplémentaire. Il n'y a donc pas lieu de prendre en compte cet argument.
Le recourant indique encore qu'il n'y a rien à déduire, quant à la force probante de l'agenda électronique, de la disponibilité affichée par l'intimée. Cette argumentation est manifestement insuffisante au regard de l'<ref-law>. Au demeurant, c'est à juste titre que la cour cantonale a examiné si les données contenues dans cet agenda étaient crédibles au regard de la situation du cas d'espèce, notamment des jours supplémentaires effectués par une autre employée et de la disponibilité avérée de l'intimée.
S'agissant de la quotité - contestée - des heures mensuelles effectuées dans le cadre du second emploi de l'intimée, elle ne saurait infléchir le résultat de l'administration des preuves, dès lors qu'il n'est pas contesté que l'intimée, qui se montrait particulièrement disponible et serviable, avait plus d'opportunité que ses deux autres collègues secrétaires et que, de ce fait, elle a pu effectuer autant, sinon plus de jours supplémentaires de travail que B._, dont il a été admis que la surcharge était importante.
La critique se rapportant à l'engagement d'une nouvelle secrétaire à plein temps, qui confirme la surcharge de travail, est également vaine. Comme il a été admis par l'employeur que l'intimée devait effectuer des heures supplémentaires, l'existence d'une surcharge de travail n'est, en effet, pas litigieuse.
L'ensemble des critiques du recourant relatives aux divers éléments d'appréciation, sur lesquels la cour a pris appui pour conclure que l'agenda électronique revêtait une force probante suffisante, ont été rejetées. Par conséquent, le recourant ne parvient pas à démontrer que l'appréciation de la cour est arbitraire.
3. Le recourant fait grief à la juridiction cantonale d'avoir violé l'<ref-law>. Il considère que l'intimée n'a nullement rempli les réquisits de cette disposition légale, en ayant omis de soumettre régulièrement à l'employeur des décomptes d'heures supplémentaires. Il prétend aussi que la « règle de sauvegarde » énoncée par le Tribunal fédéral dans l'<ref-ruling> ne trouve pas application dans le cas d'espèce. S'en prévalant à tort, le Tribunal cantonal a enfreint l'<ref-law>.
En l'occurrence, il a été retenu que des heures supplémentaires ont été imposées par l'employeur, qui exigeait qu'une secrétaire soit toujours présente durant les heures d'ouverture du bureau. Pour les heures supplémentaires qui n'étaient pas expressément imposées, les juges valaisans ont arrêté que l'employeur avait connaissance que l'intimée effectuait ces heures et qu'il les avait au moins tacitement acceptées.
Sur la base de cet état de fait, il est constant que l'employeur ne pouvait pas ignorer que l'intimée effectuait des heures supplémentaires en cas d'absence des autres employées, puisqu'il avait lui-même imposé ce système de remplacement. Il ne pouvait également lui échapper, s'agissant des heures non expressément imposées, que le temps convenu ne suffisait pas pour exécuter les tâches confiées à l'intimée. Dans ces circonstances et quoi qu'en pense le recourant, il est de jurisprudence que l'employeur n'a pas d'intérêt à être avisé immédiatement, la prétention étant soumise à la prescription quinquennale de l'<ref-law> - sous réserve de l'abus de droit (<ref-ruling> consid. 2.3 et 2.4 et les références citées). De même, lorsque, comme en l'espèce, les rapports de travail ont pris fin, l'employeur n'a en général pas d'intérêt pressant à être informé des heures supplémentaires effectuées (<ref-ruling> consid. 2.4).
Dès lors que le recourant ne prétend pas que le comportement de l'employée est abusif et, encore moins, que la prétention de l'intimée est prescrite, force est de conclure que la cour cantonale n'a pas violé le droit fédéral en ayant décidé que l'intimée pouvait prétendre à la rémunération des jours de travail supplémentaire effectués.
Contrairement à ce que soutient le recourant, il est donc sans pertinence, pour trancher la question de droit litigieuse, que l'intimée n'ait fait valoir qu'occasionnellement les jours de travail supplémentaire allégués. Par ailleurs, lorsque le recourant prétend que l'intimée ne pouvait espérer compenser les heures supplémentaires par du temps libre, il semble oublier que l'intimée avait pris en trop 42 jours de vacances et qu'en déduisant ces 42 jours de ses prétentions, l'intimée a admis avoir compensé, de son propre chef, une partie des jours supplémentaires effectués.
Ainsi, le grief développé par le recourant est infondé.
4. Le dernier moyen soulevé a trait à l'existence d'un accord tacite.
Dans son argumentation, lors même que le recourant reproche à l'autorité cantonale de s'être écartée des allégations relatives à un accord tacite entre les parties sur la compensation en nature des jours de travail supplémentaire, il ne fait état d'aucune violation du droit de procédure cantonal. Il ne soulève pas plus une exception au sens de l'<ref-law>. Il se contente en définitive de dire qu'une transaction relative à la rétribution d'heures supplémentaires ne nécessite pas la forme écrite de l'<ref-law> et qu'il est abusif, compte tenu des circonstances d'espèce, soit notamment de la relation amoureuse qui existait entre les parties et de l'absence de revendications judiciaires avant la cessation de cette relation, d'estimer qu'il n'y pas eu d'accord informel, transactionnel entre les parties. Il va sans dire qu'une telle démonstration est irrecevable, puisque le recourant s'éloigne des constatations de fait de l'autorité cantonale et qu'il n'explique, de surcroît, pas en quoi l'acte attaqué viole le droit (<ref-law>).
5. Au terme de cet examen, le recours ne peut qu'être rejeté dans la mesure de sa recevabilité.
6. Compte tenu de l'issue du litige, les frais judiciaires, calculés par application de l'art. 65 al. 4 let. c LTF, seront mis à la charge du recourant, qui succombe (<ref-law>). Celui-ci versera à l'intimée une indemnité à titre de dépens (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 800 fr., sont mis à la charge du recou-rant.
3. Une indemnité de 2'500 fr., à payer à l'intimée à titre de dépens, est mise à la charge du recourant.
4. Le présent arrêt est communiqué en copie aux mandataires des parties et à la Cour civile II du Tribunal cantonal du canton du Valais.
Lausanne, le 8 janvier 2008 / CMF
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
Le Président: La Greffière:
Corboz Crittin