Faits: A. A.a Par contrat du 7 octobre 1976, les SI D._, E._, F._, G._, H._ ont engagé dès le 1er novembre 1976 (art. 64 al. 2 OJ) les époux A.W._ et B.W._ (les demandeurs) en qualité de concierges d'immeubles sis au chemin R._, à Genève. Le contrat prévoyait qu'un appartement de 4 pièces situé au 1er étage de l'un des immeubles serait attribué aux prénommés à titre de logement de fonction. B.W._ étant devenue dès le 1er novembre 1992 totalement incapable de travailler pour raisons médicales, le contrat de travail n'a été maintenu, selon un avenant du 6 octobre 1992, qu'entre les sociétés propriétaires et A.W._. Au 1er novembre 2000, le loyer se montait à 10'872 fr. par an (906 fr. par mois), charges non comprises. A.b Au cours de l'année 2001, A.W._ a informé la SI F._ (la défenderesse) qu'il se trouverait à son tour en incapacité totale de travail dès le 1er novembre 2001. La représentante de la défenderesse a alors établi le 9 août 2001 un contrat de bail à loyer liant la SI F._ et les demandeurs, lequel portait sur l'appartement que ces derniers occupaient jusqu'alors; le bail entrait en vigueur le 1er novembre 2001. Le loyer a fait l'objet d'un avis de fixation officielle daté du 8 août 2001, qui le portait à 15'600 fr. par an (1'300 fr. par mois) à partir du 1er novembre 2001, charges non comprises. Il a été retenu que les demandeurs ont reçu le contrat de bail et l'avis officiel au plus tard le 5 septembre 2001. B. Le 24 octobre 2001, les époux A.W._ et B.W._ ont saisi la Commission de conciliation en matière de baux et loyers d'une requête en contestation du loyer initial. Ils ont allégué que ce loyer était abusif et requis un calcul de rendement, le loyer de l'appartement devant être fixé à 10'872 fr. par an, sans les charges, dès le 1er novembre 2001. La conciliation ayant échoué, la cause a été portée par les locataires devant le Tribunal genevois des baux et loyers. Devant cette instance, les demandeurs, sur la base d'un nouveau calcul, ont conclu à ce que le loyer admissible soit fixé à 5'496 fr. par an; ils ont également présenté une demande additionnelle tendant à l'exécution de divers travaux d'entretien. Par jugement du 28 novembre 2003, le Tribunal des baux et loyers a estimé que les conditions de recevabilité de l'action en contestation du loyer initial étaient réunies. Procédant à un calcul de rendement, il a arrêté le loyer admissible à 5'568 fr. par an. Le tribunal a encore rejeté la demande concernant les travaux d'entretien. Saisie d'un appel de la défenderesse, la Chambre d'appel en matière de baux et loyers de Genève, par arrêt du 14 mars 2005, a annulé le jugement précité et, statuant à nouveau, dit que le loyer de l'appartement occupé par les demandeurs est fixé à 15'600 fr. l'an, charges non comprises, dès le 1er novembre 2001. En substance, la cour cantonale a considéré que les parties étaient déjà liées par un bail portant sur le même objet, de sorte que le litige ne concernait pas la fixation d'un loyer initial, mais qu'il devait être examiné sous l'angle d'une majoration de loyer. Comme l'avis officiel a en tout cas été reçu par les locataires le 5 septembre 2001, le délai de 30 jours pour saisir la Commission de conciliation avait commencé à courir le 6 septembre 2001, si bien que la requête en contestation formée le 24 octobre 2001 était tardive. Certes, la défenderesse n'avait pas invoqué la tardiveté de la contestation devant les premiers juges. S'agissant d'un délai de péremption, le Tribunal des baux et loyers aurait toutefois dû contrôler d'office la recevabilité de ladite contestation et la rejeter pour cause de tardiveté. La Chambre d'appel en a déduit que le jugement critiqué devait être annulé, l'augmentation de loyer notifiée par la bailleresse étant validée. C. Les époux A.W._ et B.W._ recourent en réforme au Tribunal fédéral. Ils requièrent qu'il soit constaté que la requête en contestation du loyer initial est recevable, que le loyer de leur appartement soit fixé à 5'568 fr. par année, sans les charges, dès le 1er novembre 2001, que la bailleresse soit condamnée à restituer aux locataires le trop-perçu en découlant et que soit ordonnée la libération de la garantie de loyer constituée en début du bail en tant qu'elle dépasse trois mois du nouveau loyer. Subsidiairement, ils concluent au renvoi de la cause à la cour cantonale pour instruction dans le sens des considérants. Par décision incidente du 2 juin 2005, la Ire Cour civile a fait droit à la requête d'assistance judiciaire présentée par les recourants et leur a désigné l'avocate Nathalie Landry comme conseil d'office. L'intimée propose le rejet du recours et la confirmation de l'arrêt attaqué. 