Faits:
A. A.a X._ exploite en raison individuelle une pizzeria sise au ... à Genève, à l'enseigne « ... ». Le 16 janvier 2001, il a engagé Y._, en qualité de serveuse, pour un salaire mensuel brut de 3'400 francs.
A la suite d'un accident, l'employée s'est trouvée en incapacité totale de travailler, du 10 juin au 17 novembre 2002, puis dès le 14 janvier 2003.
Le 26 avril 2004, Y._ a été licenciée pour le 1er juin 2004. La résiliation du contrat de travail n'a pas été contestée.
A.b Par contrat de gérance libre signé le 1er mars 2005, X._ a remis à bail « ... » à Y._ et A._, prises conjointement et solidairement. La gérance, conclue pour une année, commençait le 1er janvier 2005; le contrat prévoyait un délai de résiliation de 6 mois. X._ a repris possession de son établissement en janvier 2006, après résiliation du contrat.
B. B.a Le 4 décembre 2006, Y._ a assigné X._ en paiement de 28'177 fr.40, soit 10'132 à titre de treizième salaire, d'indemnité pour vacances non prises, de rémunération des heures supplémentaires et d'allocations familiales pour l'année 2001, 6'665 fr.40 à titre de rémunération des heures supplémentaires pour l'année 2002 et 11'380 fr. en exécution d'un accord passé avec V._. La demanderesse réclamait en sus la délivrance de fiches de salaire et d'un décompte de vacances pour les années 2001 et 2002.
Le défendeur a conclu au rejet de la demande. Il a formé une demande reconventionnelle tendant au paiement de 8'800 fr., sous déduction de 1'847 fr.74, à titre de remboursement de prêts, de 30'000 fr. à titre d'arriérés de loyers de gérance et de 3'324 fr. à titre de remboursement d'honoraires d'avocat payés dans le cadre d'une autre procédure.
Le 24 mai 2007, le Tribunal des prud'hommes a condamné le défendeur à, d'une part, payer à la demanderesse les montants bruts de 2'429 fr.15 et de 11'380 fr., avec intérêts à 5% l'an dès le 4 décembre 2006 et, d'autre part, à lui délivrer les fiches de salaire des mois de janvier 2001 à mai 2002 et le décompte de vacances de 2002. Quant à la demanderesse, elle a été condamnée à verser au défendeur 8'800 fr. nets, avec intérêts à 5% l'an dès le 28 février 2003.
B.b Les deux parties ont saisi la Cour d'appel de la juridiction des prud'hommes, le défendeur le 28 juin 2007 et la demanderesse le 2 juillet suivant. Par arrêt du 4 janvier 2008, l'appel interjeté par le défendeur a été déclaré recevable, contrairement à celui de la demanderesse, irrecevable. Sur le fond, l'autorité cantonale a confirmé le jugement du Tribunal des prud'hommes, en précisant que la somme de 2'429 fr.15 portait intérêts à 5% l'an dès le 1er juin 2004, celle de 11'380 fr. dès le 5 février 2007 et celle de 8'800 fr. dès le 4 décembre 2006. La Cour d'appel a également dispensé le défendeur de remettre à la demanderesse les fiches de salaire des mois de janvier 2001 à mai 2002 et le décompte de vacances de 2002.
C. C.a Le défendeur exerce un recours en matière civile. Il conclut à l'annulation de l'arrêt entrepris et à sa réforme, en ce sens que la demanderesse soit déboutée de toutes ses conclusions et condamnée, s'agissant de la demande reconventionnelle, à lui verser les sommes de 8'800 fr., sous déduction de 1'847 fr.74, avec intérêts à 5% l'an dès le 28 février 2003, de 30'000 fr., avec intérêts à 5% l'an dès le 31 mars 2006 et de 3'324 fr., avec intérêts à 5% l'an dès le 31 décembre 2006. Le défendeur requiert l'octroi de l'effet suspensif.
Par pli du 27 février 2008, la demanderesse a sollicité sa mise au bénéfice de l'assistance judiciaire.
C.b Par ordonnance présidentielle du 5 mars 2008, l'effet suspensif été accordé au recours.

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 (<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>). La partie recourante qui entend s'écarter des constatations de l'autorité précédente doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (<ref-ruling> consid. 2.4). 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. Il n'est pas litigieux que les parties sont liées par un contrat de travail régi par la Convention collective nationale de travail pour les hôtels, restaurants et cafés du 6 juillet 1998 (ci-après: CCNT 98).
3. Le recourant reproche à l'autorité cantonale d'avoir fait une application arbitraire de l'art. 21 CCNT 98. Selon cette disposition, si l'employeur n'a pas tenu de registre des heures de travail et des jours de repos effectifs, le contrôle de la durée du temps de travail tenu par le collaborateur est admis comme moyen de preuve en cas de litige (cf. art. 21 al. 2 et 3 CCNT 98).
3.1 La juridiction cantonale a estimé qu'en l'absence de tout registre, il y avait lieu de se référer aux affirmations de l'employée s'agissant de la durée effectivement travaillée durant la période non prescrite. Elle a ainsi arrêté, tout comme l'instance précédente, que la période en cause couvrait huit mois, soit du 5 décembre 2001 au 10 juin 2002 et du 18 novembre 2002 au 13 janvier 2003. Sur la base d'un horaire prévu de travail hebdomadaire de quarante-deux heures, tel que ressortant des pièces et des auditions des parties, et d'un horaire effectif de neuf heures par jour ou quarante-cinq heures par semaine - de 7h à 16h30, avec une demi-heure de pause pour le repas -, la cour cantonale a comptabilisé un nombre de trois heures de travail supplémentaires par semaine, soit au total 103.92 heures (3 x 4.33 x 8) pour la période concernée.
Le recourant critique le nombre d'heures de travail - neuf par jour ou quarante-cinq par semaine - arrêté par la cour cantonale, sur la seule et unique base de la déclaration faite par l'intimée le 5 mars 2007. Il estime qu'il ne s'agit pas là d'un « contrôle de la durée du temps de travail tenu par le collaborateur » au sens de l'art. 21 al. 2 (recte: al. 3) CCNT 98, puisqu'un tel contrôle doit se présenter sous la forme d'un document écrit détaillé et non pas sous celle d'une simple déclaration orale. Il reproche en outre à la juridiction cantonale d'avoir omis de prendre en compte la déposition du témoin Arthur Duarte Da Costa E Silva, qui a affirmé que l'intimée commençait son service à 7h et le terminait à 16h, tout en ayant dûment pris sa pause de midi de 30 minutes. A lire le recourant, sur la base de cette déposition, le nombre d'heures supplémentaires effectuées par l'intimée s'élève au maximum, en reprenant les calculs de la Cour d'appel des prud'hommes, à 17.32 heures, ce qui représente 404 fr.90. Enfin, le recourant évoque une violation de l'<ref-law>, sans autre explication.
3.2 Comme il est constant qu'aucun registre des heures de travail n'a été tenu par l'employeur, contrairement aux exigences de l'art. 21 al. 2 CCNT 98, l'autorité cantonale pouvait se fonder sur le contrôle de la durée du temps de travail tenu par le collaborateur.
L'intimée a allégué avoir effectué 276 heures supplémentaires du 1er janvier 2002 au 31 mai 2002 et produit un décompte manuscrit qui indiquait le nombre d'heures effectuées pour ces mois de travail. Sur la base des dires de l'intimée en audience d'instruction, qui a notamment précisé l'horaire de travail quotidien, et du contenu de la déposition d'un témoin, la cour cantonale a toutefois retenu un nombre d'heures supplémentaires inférieur à celui allégué.
Dès lors qu'il n'est pas contesté que l'intimée a accompli des heures supplémentaires par rapport à l'horaire contractuellement convenu, l'autorité cantonale pouvait - à défaut de décompte précis établi par l'employeur et donc de moyen de déterminer le nombre effectif d'heures supplémentaires accomplies - procéder, par application analogique de l'<ref-law>, à une estimation sur la base des éléments dont elle disposait. On ne voit pas en quoi l'autorité cantonale aurait violé le droit fédéral en axant son estimation sur la base des éléments susmentionnés. Le présent recours ne démontre en particulier pas dans quelle mesure il serait choquant de s'en tenir à l'horaire journalier, tel que décrit en audience par l'intimée. Contrairement à ce que soutient le recourant, le seul témoin entendu en instance cantonale ne contredit en rien la déclaration de l'intimée, dès lors qu'il a indiqué que « la serveuse du matin commençait dès l'ouverture, soit à 7h, et finissait vers 16h » et non pas à 16h, comme repris par le recourant dans son écriture de recours. Au demeurant, il ne ressort pas du dossier que l'employée effectuait des horaires de travail irréguliers et qu'elle n'aurait ainsi pas pu les mémoriser et les relater par voie orale - ce que le recourant ne prétend du reste pas. Dans ces circonstances, il n'est pas insoutenable, pour la cour cantonale, de s'être référée aux horaires invoqués en audience par l'intimée pour calculer les heures supplémentaires.
S'agissant de la violation de l'<ref-law>, brièvement invoquée au terme du grief, force est d'admettre que le recourant n'établit pas dans quelle mesure cette disposition aurait été violée par les magistrats cantonaux.
Si tant est qu'il soit recevable, le grief est donc infondé.
4. Sous l'intitulé « des prétentions relatives aux prestations de V._ », le recourant reproduit le contenu des <ref-law> et 321e al. 1 CO. Il ne dénonce toutefois pas une violation de ces dispositions, ni aucune autre violation du droit fédéral. Le recourant assoit son argumentation sur le dommage qu'il dit avoir subi à la suite du comportement adopté par l'intimée envers le tiers V._, dommage qu'il chiffre à 9'532 fr.36. En définitive, le recourant s'en prend aux constatations de fait. Or, sans même évoquer l'arbitraire, il se contente de discourir d'une manière toute générale en fondant son raisonnement sur des faits qui ne ressortent pas du jugement entrepris; aucune référence n'est faite à des moyens de preuve qui auraient été occultés, de manière insoutenable, par l'autorité cantonale. L'arbitraire dans l'appréciation des preuves et les constatations de fait en découlant n'est donc en aucun cas démontré. Cela étant, le grief est infondé, sans qu'il ne soit opportun de l'examiner plus avant.
5. Les autres griefs soulevés par le recourant sont développés sous le titre « De la demande reconventionnelle ». Le recourant débute sa critique par un rappel de la jurisprudence fédérale rendue en matière de compensation, au sens de l'<ref-law>. Puis, pour contrecarrer le raisonnement de la Cour d'appel se rapportant tant aux arriérés de loyers qu'aux dommages-intérêts, il s'en prend d'abord aux considérations émises par l'autorité cantonale sur le bien-fondé des conclusions reconventionnelles, avant de prétendre qu'il existe un rapport de connexité entre le contrat de travail et le contrat de gérance.
5.1 La Cour d'appel a confirmé le jugement du Tribunal des prud'hommes, en précisant les dates à partir desquelles les intérêts commençaient à courir et en dispensant le recourant de remettre à l'employée les fiches de salaire de janvier 2001 à mai 2002 et le décompte de vacances de 2002. La cour cantonale a ainsi confirmé l'irrecevabilité des prétentions reconventionnelles en paiement de 30'000 fr. à titre de loyers de gérance, pour cause d'incompétence de la juridiction des prud'hommes. A cet égard, elle a nié que le litige lié au contrat de gérance était en relation directe avec le contrat de travail, en relevant que ce dernier contrat, qui fonde la demande principale, a pris fin au 1er juin 2004, alors que le contrat de gérance n'a été signé qu'en mars 2005. La juridiction cantonale a en sus retenu que les prétentions issues du contrat de gérance étaient supérieures à celles qui découlent du contrat de travail et qu'il n'y avait donc pas lieu d'argumenter dans le sens d'une prépondérance du contrat de travail, fondant l'attraction de compétence. Quant au paiement de dommages-intérêts pour les frais d'avocat, le dispositif de l'arrêt entrepris confirme le rejet des prétentions y relatives, lors même que la motivation de ce même arrêt fait état d'incompétence de la juridiction des prud'hommes pour trancher cette question, avant d'argumenter sur le bien-fondé de la prétention. Les juges cantonaux ont encore observé que, s'ils avaient dû examiner le bien-fondé des conclusions du recourant, celles-ci auraient dû être écartées, à défaut de démonstration suffisante.
5.2 En lien avec l'incompétence ratione materiae de la juridiction des prud'hommes pour juger de la prétention reconventionnelle en paiement des loyers de gérance, le recourant n'invoque aucune violation du droit de procédure cantonal, qui régit les règles de compétence matérielle. Il se contente d'alléguer qu'il existe un rapport de connexité entre le contrat de travail et le contrat de gérance, sans même revenir sur les arguments développés par la cour cantonale. Il va sans dire qu'une telle démonstration, qui n'énonce même pas quelle est la violation incriminée, est insuffisante. Le grief est irrecevable. Dans la mesure où l'autorité cantonale a donc confirmé l'irrecevabilité des prétentions en paiement des arriérés de loyers, il n'est pas nécessaire d'examiner la critique sous l'angle du bien-fondé de la demande reconventionnelle.
Quant à la prétention en dommages-intérêts fondée sur le paiement d'une note d'honoraires, contrairement à celle en paiement des arriérés de loyers, aucune sanction d'irrecevabilité n'a été prononcée - sans qu'une éventuelle violation du droit n'ait été soulevée sur ce point. Par conséquent, il y a lieu d'examiner les arguments au fond développés par le recourant. La cour cantonale a observé que la prétention litigieuse n'a fait l'objet d'aucune démonstration, alors que le fardeau de la preuve de son existence et de son étendue appartenait au recourant. Elle a, en particulier, relevé qu'aucun état de compte n'a été produit et que la note d'honoraires n'a été avalisé par quiconque. Après avoir rappelé le contenu de l'<ref-law>, le recourant se contente d'affirmer que « l'on ne voit pas pourquoi cette note d'honoraires aurait dû être avalisée par quiconque afin de valoir comme moyen de preuve », sans même dénoncer une violation du fardeau de la preuve. Une fois encore, le moyen est irrecevable, puisqu'il ne satisfait nullement à l'exigence de motivation contenue à l'<ref-law>.
5.3 Sur la question de la compensation, le recourant ne soulève qu'une seule critique. Il prétend que, dès lors qu'il a expressément déclaré compenser sa créance de 30'000 fr., respectivement de 3'324 fr., avec les montants dont il pourrait être redevable à l'encontre de l'intimée, « la Cour d'appel des prud'hommes ne saurait purement et simplement écarter les prétentions du recourant au motif qu'elle serait incompétente à raison de la matière ». Il précise, pour la seule prétention d'arriérés de loyers, que la juridiction cantonale devait statuer sur l'exception de compensation ou différer l'effet exécutoire de sa décision en fixant un délai au recourant pour faire valoir sa contre-réclamation devant la juridiction compétente. Quoi qu'en pense le recourant, la cour cantonale a tranché la question de la compensation. Dans le considérant consacré aux prétentions de l'intimée se rapportant aux prestations de l'assurance V._, versées en main de l'employeur, les juges cantonaux ont indiqué que le recourant n'avait pas démontré de façon claire qu'il détenait contre son ex-employée une créance exigible, immédiatement opposable en compensation. La cour cantonale s'est donc bien prononcée sur la question de la compensation. Cela étant, la critique du recourant tombe manifestement à faux.
Au demeurant, il a été relevé plus haut que l'autorité cantonale a jugé que la prétention en dommages-intérêts n'a fait l'objet d'aucune démonstration. Elle ne saurait donc être opposée en compensation. En ce qui concerne la créance constituée des loyers de gérance, le recourant n'explique pas, sous l'angle de la compensation, en quoi le droit fédéral aurait été violé; il se contente de reprendre les arguments développés en appel, sans même soutenir que la créance compensante était suffisamment claire pour être valablement prise en considération. Tel ne saurait, de toute manière, être le cas: si le recourant prétend que la créance alléguée correspond aux loyers de gérance, référence faite à la convention y relative, il n'apporte toutefois aucune précision sur le montant de la créance, qui ne correspond à aucune donnée concrète. Le recourant se contente d'alléguer que « l'intimée n'a pas quitté les lieux à l'échéance du bail, mais uniquement au courant du mois de mars 2006 ». Or, une telle allégation, modifiée en cours d'instance - le mois de mars 2006 a été remplacé par le mois de janvier 2006 -, n'apporte aucune précision sur les loyers impayés. Le montant articulé de 30'000 fr. n'a du reste même pas été modifié en cours d'instance, lors même que la durée d'occupation des locaux loués a été revue à la baisse. A défaut de plus amples précisions, la dette du recourant n'avait donc pas à être compensée avec la créance alléguée.
Il en découle que le grief est mal fondé.
6. Le recourant reproche enfin aux juges cantonaux d'avoir arbitrairement violé le principe de l'interdiction de la reformatio in pejus.
En dépit de ce que semble penser le recourant, l'interdiction de la reformatio in pejus n'est pas une garantie de droit constitutionnel et ce sont les règles cantonales de procédure qui peuvent l'admettre ou la rejeter et qui en déterminent la portée. Le grief de la reformatio in pejus par rapport au jugement de première instance relève donc du droit cantonal de procédure.
Dès lors que le recourant ne fait état d'aucune application arbitraire d'une disposition du droit cantonal interdisant la reformatio in pejus, la critique est irrecevable (cf. <ref-law>).
7. Il résulte des considérants qui précèdent que le recours en matière civile doit être rejeté dans la mesure de sa recevabilité.
8. 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). L'intimée ayant produit, par l'intermédiaire de son avocat, une très brève écriture, il se justifie de lui allouer des dépens réduits.
La demande d'assistance judiciaire déposée par l'intimée doit être admise dans la mesure où elle n'a pas perdu son objet, dès lors que le risque existe pour l'intéressée de ne pouvoir recouvrer les dépens auxquels elle a droit; son avocat sera désigné comme avocat d'office.

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 à 2'000 fr., sont mis à la charge du recourant.
3. Une indemnité de 200 fr., à payer à l'intimée, à titre de dépens réduits, est mise à la charge du recourant.
4. La demande d'assistance judiciaire de l'intimée est admise, autant qu'elle n'est pas sans objet, et Me Michael Anders est désigné comme avocat d'office.
5. Au cas où les dépens ne pourraient être recouvrés, la caisse du Tribunal fédéral versera au mandataire de l'intimée une indemnité de 200 fr. à titre d'honoraires d'avocat d'office.
6. Le présent arrêt est communiqué aux mandataires des parties et à la Cour d'appel de la juridiction des prud'hommes du canton de Genève.
Lausanne, le 4 juin 2008
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
Le Président: La Greffière:
Corboz Crittin