Faits:
A. Ressortissants de la République démocratique du Congo (ci-après: le Congo), X._, né en 1993, et sa soeur, Y._, née en 1996, sont arrivés en Suisse le 30 janvier 2003. Le 31 janvier 2003, leur oncle, Z._, ressortissant congolais titulaire d'une autorisation d'établissement en Suisse, a déposé des demandes d'autorisations de séjour en leur faveur. Il a expliqué que ces enfants étaient orphelins et qu'avant de mourir, leur mère avait souhaité qu'ils aillent vivre en Suisse chez sa soeur - soit la femme de Z._. Un compatriote qui s'exilait en Amérique du Nord les avait amenés en Suisse comme ses propres enfants, conformément aux voeux exprimés par leur mère dans son "testament". Z._ a assuré que ses enfants étaient d'accord d'accueillir leurs cousins et il a produit différentes pièces à l'appui de sa requête.
Il s'en est suivi un échange de courriers sur plusieurs années entre Z._ et le Service de la population du canton de Vaud (ci-après: le Service cantonal). Ce dernier a notamment demandé des compléments d'information ainsi qu'un certain nombre de documents, qu'il a ensuite soumis à l'Ambassade de Suisse à Kinshasa pour authentification. Ladite ambassade a attiré l'attention du Service cantonal sur le risque que X._ et Y._ fassent l'objet d'un trafic d'enfants et elle a insisté pour que les intéressés produisent une preuve matérielle du décès des parents, dès lors que les jugements supplétifs d'actes de décès produits avaient été établis seulement sur la base des dires d'une tante de X._ et Y._ restée au Congo. Les intéressés n'ont pas réussi à produire les documents requis dans l'ultime délai qui leur avait été fixé au mois de décembre 2008.
Dans l'intervalle, la Justice de paix du Cercle de Lausanne a nommé, le 1er juillet 2004, Z._ en tant que tuteur de X._ et Y._. Par ailleurs, Z._ et sa femme, A._, qui ne remplissaient pas les conditions du droit congolais pour adopter leurs neveux puisqu'ils avaient déjà trois enfants, ont adressé, le 12 février 2008, une demande de dispense en vue d'adoption à l'Ambassade du Congo en Suisse.
Le 20 mai 2009, le Service cantonal a refusé les autorisations de séjour requises et imparti à X._ et Y._ un délai de départ d'un mois dès la notification de cette décision.
B. X._ et Y._ ont alors porté leur cause devant la Cour de droit administratif et public du Tribunal cantonal vaudois (ci-après: le Tribunal cantonal) qui, par arrêt du 28 septembre 2009, a rejeté leur recours et confirmé la décision du Service cantonal du 20 mai 2009. Le Tribunal cantonal a examiné le cas des intéressés sous l'angle de l'art. 35 de l'ordonnance du 6 octobre 1986 limitant le nombre des étrangers en vigueur jusqu'au 31 décembre 2007 (OLE; RO 1986 1791), en relation avec l'art. 6 de l'ordonnance du 19 octobre 1977 réglant le placement d'enfants à des fins d'entretien et en vue d'adoption (OPEE; RS 211.222.338). Il a notamment souligné que X._ et Y._ étaient arrivés en Suisse illégalement et qu'on ne pouvait pas retenir comme établi qu'ils étaient orphelins. Les juges cantonaux ont aussi considéré que les intéressés n'avaient pas démontré être dans une situation de détresse personnelle.
C. Le 30 octobre 2009, X._ et Y._ ont déposé au Tribunal fédéral un recours en matière de droit public et un recours constitutionnel subsidiaire à l'encontre de l'arrêt du Tribunal cantonal du 28 septembre 2009. Ils concluent, sous suite de frais et dépens, à l'annulation de l'arrêt attaqué. En outre, ils demandent, principalement, l'annulation de la décision du Service cantonal du 20 mai 2009 ainsi que la délivrance des autorisations de séjour requises et, subsidiairement, le renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants. Ils se plaignent de violation des art. 35 OLE et 6 OPEE ainsi que d'arbitraire et de violation du droit d'être entendu. Ils sollicitent l'assistance judiciaire.
Le Tribunal cantonal se réfère à l'arrêt attaqué. Le Service de la population a renoncé à déposer des déterminations.
L'Office fédéral des migrations propose de déclarer irrecevable le recours en matière de droit public et de rejeter le recours constitutionnel subsidiaire dans la mesure de sa recevabilité.
D. Par ordonnance du 5 novembre 2009, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif contenue dans le recours.

Considérant en droit:
1. Le présent litige porte sur des demandes d'autorisations de séjour déposées le 31 janvier 2003, soit avant l'entrée en vigueur, le 1er janvier 2008, de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20). C'est par conséquent à juste titre que le Tribunal cantonal a appliqué l'ancien droit des étrangers en l'espèce (cf. art. 126 al. 1 LEtr).
2. Le Tribunal fédéral examine d'office sa compétence (<ref-law>). Il contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 96).
Les recourants ont interjeté, en un seul acte conformément à l'<ref-law>, un recours en matière de droit public et un recours constitutionnel subsidiaire. Le second étant irrecevable en cas de recevabilité du premier (<ref-law>), il convient d'examiner si la voie du recours en matière de droit public est ouverte.
3. Selon l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit.
Les recourants concluent à l'octroi d'autorisations de séjour en invoquant l'art. 35 OLE, en relation avec l'art. 6 OPEE. Or, l'art. 35 OLE, pas plus d'ailleurs qu'aucune autre disposition de l'OLE, ne peut fonder un droit à l'obtention d'une autorisation de séjour (cf. arrêt 2P.18/2007 du 29 juin 2007 consid. 3.1). Sinon, l'OLE ne serait pas compatible avec l'art. 4 de la loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers en vigueur jusqu'au 31 décembre 2007 (LSEE; RS 1 113), qui accorde à l'autorité cantonale compétente un pouvoir de libre appréciation, le refus d'autorisation étant définitif (art. 18 al. 1 LSEE; cf. <ref-ruling> consid. 2.1 p. 284). Partant, les recourants ne peuvent, sous l'angle de l'art. 83 let. c ch. 2 LTF, se plaindre d'une violation des art. 35 OLE et/ou 6 OPEE.
La législation fédérale sur les étrangers ne contient aucune autre disposition propre à conférer aux recourants un droit à séjourner en Suisse. Les recourants ne se prévalent du reste que des art. 35 OLE et 6 OPEE.
Les recourants invoquent par ailleurs l'interdiction de l'arbitraire et leur droit d'être entendus. Ils ne font donc valoir aucune violation de droits fondamentaux qui découleraient de la Constitution ou de la CEDH et seraient de nature à leur conférer un droit de séjour en Suisse. Ils ne se sont du reste jamais réclamés de tels droits au cours de la procédure cantonale.
Le recours en matière de droit public doit donc être déclaré irrecevable au regard de l'art. 83 let. c ch. 2 LTF.
4. 4.1 Reste à examiner le recours constitutionnel subsidiaire. Un tel recours doit être dirigé contre une décision finale (<ref-law> applicable par renvoi de l'<ref-law>), de sorte que le présent recours est irrecevable dans la mesure où il tend à l'annulation de la décision du Service cantonal du 20 mai 2009. De plus, le recours constitutionnel subsidiaire ne peut être formé que pour violation des droits constitutionnels (<ref-law>), grief que le recourant doit invoquer et motiver suffisamment sous peine d'irrecevabilité (<ref-law> applicable par renvoi de l'<ref-law>). En outre, le recourant doit avoir un intérêt juridique à l'annulation ou à la modification de la décision attaquée (<ref-law>). Un recourant n'a qualité pour former un recours constitutionnel subsidiaire que si les dispositions légales dont il dénonce l'application arbitraire lui accordent un droit ou servent à protéger ses intérêts prétendument lésés (cf. <ref-ruling> consid. 6.1 p. 197 s. et 6.3 p. 200). Selon la jurisprudence en effet, l'interdiction générale de l'arbitraire découlant de l'art. 9 Cst. ne confère pas, à elle seule, une position juridique protégée au sens de l'<ref-law> (cf. <ref-ruling> consid. 4 à 6 p. 191 ss). Dès lors que X._ et Y._ n'ont pas droit à des autorisations de séjour (cf. consid. 3, ci-dessus), ils ne sont pas habilités à agir par la voie du recours constitutionnel subsidiaire pour critiquer, sous l'angle de l'arbitraire, l'application de l'art. 35 OLE en relation avec l'art. 6 OPEE.
4.2 Le recours constitutionnel subsidiaire permet toutefois aux recourants qui, comme en l'espèce, n'ont pas la qualité pour agir au fond de se plaindre de la violation de leurs droits de partie équivalant à un déni de justice formel, pour autant que, par ce biais, ils n'invoquent pas, même indirectement, des moyens ne pouvant être séparés du fond (cf. <ref-ruling> consid. 6.2 p. 198 s.; voir aussi <ref-ruling> consid. 1.4 p. 222).
5. Invoquant l'art. 29 al. 2 Cst., les recourants reprochent au Tribunal cantonal d'avoir violé leur droit d'être entendus, en ne procédant pas à l'audition requise de deux personnes, Z._, leur tuteur, et B._, un ami de la famille qui les avait aidés dans certaines démarches.
5.1 Le droit d'être entendu garanti constitutionnellement comprend notamment le droit pour l'intéressé de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, de participer à l'administration des preuves essentielles ou, à tout le moins, de s'exprimer sur son résultat lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 2.2 p. 190; <ref-ruling> consid. 5.1 p. 293 et la jurisprudence citée). A lui seul, l'art. 29 al. 2 Cst. ne confère pas le droit d'être entendu oralement (<ref-ruling> consid. 5.3 p. 148; <ref-ruling> consid. 2.1 p. 428). Au surplus, la jurisprudence admet que le droit d'être entendu n'empêche pas l'autorité de mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient pas l'amener à modifier son opinion (<ref-ruling> consid. 5.3 p. 148; <ref-ruling> consid. 2.1 p. 429). En particulier, écarter de la sorte une requête d'audition de témoin ne viole pas l'art. 29 al. 2 Cst. (cf. ATF <ref-ruling> consid. 2.1 p. 428 s.).
5.2 Les recourants ont pu déposer devant le Tribunal cantonal un recours et un mémoire complémentaire ainsi que les pièces qu'ils jugeaient utiles. Ils ont demandé l'audition de deux personnes pour étayer des faits qu'ils avaient allégués et qui étaient donc connus des juges cantonaux. Dans ces conditions, le Tribunal cantonal pouvait s'estimer suffisamment renseigné pour statuer sans donner suite à la réquisition d'instruction des recourants, conformément à la jurisprudence rappelée ci-dessus. Ce faisant, il n'a pas violé le droit d'être entendus des recourants.
6. Le cas d'espèce a ceci de particulier que la procédure devant le Service cantonal a duré plus de six ans, ce qui est extrêmement long. Or, pendant ces six années, les deux enfants ont vécu en Suisse. Certes, Z._ et A._ n'ont pas toujours collaboré avec beaucoup de zèle, lorsque le Service cantonal leur demandait notamment la production de pièces ou le versement d'une avance de frais. Ils ont eux-même contribué à la prolongation de la procédure en requérant des délais supplémentaires. Dans ces circonstances, on ne peut admettre que les recourants puissent déduire de la lenteur des autorités une assurance ou des attentes particulières qui leur permettraient d'obtenir une autorisation de séjour (cf. <ref-ruling> consid. 3a p. 387; arrêt 2C_126/2007 du 18 juin 2007 consid. 2.7). Il n'en demeure pas moins que le Service cantonal n'a pas non plus fait preuve de la diligence que l'on pouvait attendre de lui dans le suivi du dossier, tardant en particulier à réitérer ses requêtes auprès des intéressés et des autorités. Pourtant, lorsqu'il s'agit de rendre des décisions concernant le séjour d'enfants, les autorités administratives, en particulier en matière de police des étrangers, doivent tenir compte en premier lieu de l'intérêt desdits enfants, comme le prescrit l'art. 3 par. 1 de la convention du 20 novembre 1989 relative aux droits de l'enfant (RS 0.107). Or, il est évident que plus le temps passe, plus il sera humainement difficile de prononcer une décision qui a pour résultat de modifier le lieu de séjour de l'enfant. Le fait que le Service cantonal n'ait statué sur les demandes d'autorisations de séjour que plus de six ans après leur dépôt ne peut donc être occulté. On peut dès lors se demander si, compte tenu de l'écoulement du temps, on ne se trouve pas dans une situation permettant de retenir l'existence d'un cas de rigueur au sens des art. 13 let. f OLE/30 LEtr. De par la volonté du législateur, cette question, relève toutefois de l'appréciation des autorités cantonales - sous réserve, le cas échéant, de l'approbation des autorités fédérales -, de sorte que la Cour de céans ne peut statuer sur ce point. Il appartient aux recourants de décider s'ils veulent entreprendre des démarches sous cet angle.
7. Au vu de ce qui précède, il convient de déclarer irrecevable le recours en matière de droit public et de rejeter, dans la mesure où il est recevable, le recours constitutionnel subsidiaire.
Les conclusions des recourants étaient dépourvues de toute chance de succès, de sorte qu'il convient de leur refuser l'assistance judiciaire (<ref-law>). Toutefois, compte tenu des circonstances, il ne sera pas mis de frais judiciaires à la charge des recourants (art. 66 al. 1 2ème phrase LTF). En outre, il ne sera pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière de droit public est irrecevable.
2. Le recours constitutionnel subsidiaire est rejeté dans la mesure où il est recevable.
3. La demande d'assistance judiciaire est rejetée.
4. Il n'est pas perçu de frais judiciaires.
5. Le présent arrêt est communiqué au mandataire des recourants, au Service de la population et à la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 22 mars 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Müller Dupraz