Faits:
A. Les époux X._, se sont mariés à Genève le 17 avril 2002. Le couple a deux enfants, A._, né en 2004, et B._, née en 2008 - après l'introduction de la présente procédure.
X._ est également le père de C._, né en 1990 d'une précédente union.
X._ a quitté le domicile conjugal le 27 janvier 2008.
B. B.a Par requête déposée le 31 janvier 2008 auprès du greffe du Tribunal de première instance du canton de Genève, dame X._ a sollicité des mesures protectrices de l'union conjugale ainsi que des mesures préprovisoires urgentes.
Statuant sur ces dernières le 18 février 2008, le Président du Tribunal de première instance a notamment autorisé les époux à vivre séparés, attribué à dame X._ la garde de l'enfant A._ et condamné X._ à verser en mains de son épouse, par mois et par avance, allocations familiales non comprises, un montant de 486 fr. à titre de contribution à l'entretien à la famille.
B.b Par jugement du 15 octobre 2008, statuant sur mesures protectrices de l'union conjugale, le Tribunal de première instance a, entre autres, attribué la garde des deux enfants à leur mère et condamné X._ à verser à son épouse, par mois et par avance, allocations familiales non comprises, la somme de 500 fr. du 28 janvier 2008 au 27 avril 2008 à titre de contribution à l'entretien de A._, puis, dès le 28 avril 2008, la somme de 350 fr. par enfant à titre de contribution à l'entretien de A._ et B._. Le Tribunal de première instance a par ailleurs invité X._ a introduire une action en modification de la contribution d'entretien de son fils aîné C._, ce que X._ a indiqué avoir fait.
Sur appel de X._, la Cour de justice a confirmé le jugement du Tribunal de première instance par arrêt du 20 février 2009.
C. Contre cette dernière décision, X._ (ci-après le recourant) interjette, le 27 mars 2009, un recours constitutionnel subsidiaire devant le Tribunal fédéral. Il conclut à l'annulation de l'arrêt rendu par la cour cantonale en tant qu'il le condamne au versement d'une contribution d'entretien en faveur de ses enfants d'un montant mensuel de 500 fr., puis 700 fr. dès la naissance de sa fille, demandant que ladite contribution soit réduite à 300 fr. par mois du 28 janvier 2008 au 27 avril 2008, puis à 600 fr. par mois dès le 27 avril 2008. Le recourant estime que la décision cantonale est arbitraire. Il reproche aux juges cantonaux d'avoir arbitrairement constaté les faits, soutenant qu'ils auraient commis une erreur de calcul dans l'addition de ses charges, obtenant ainsi un résultat inférieur à leur montant réel et le condamnant dès lors au paiement de contributions d'entretien dont la somme entamerait son minimum vital.
Appelée à se déterminer, dame X._ (ci-après l'intimée) s'en rapporte à la justice, relevant néanmoins qu'elle doute de la recevabilité et du bien-fondé du recours interjeté par son mari.
La Cour de justice a quant à elle admis son erreur de calcul, mais a relevé que celle-ci ne changeait rien au résultat auquel elle était parvenue. Elle a jugé que le recourant disposait en effet d'un solde disponible lui permettant d'assurer non seulement l'entretien mensuel de A._ et B._, mais également celui de son fils aîné C._, la cour cantonale soulignant toutefois qu'il ne lui appartenait pas de se prononcer sur le montant précis auquel avait droit ce dernier.
Sans y être invité, le recourant a déposé une réplique le 16 mai 2009.
D. La requête d'effet suspensif présentée par le recourant a été rejetée par ordonnance présidentielle du 1er avril 2009.

Considérant en droit:
1. La décision de mesures protectrices de l'union conjugale attaquée (<ref-law>) est une décision en matière civile au sens de l'<ref-law> (<ref-ruling> consid. 2). Elle est finale selon l'<ref-law> puisque son objet est différent de celui de la procédure de divorce qui pourrait suivre et qu'elle met fin à l'instance sous l'angle procédural (<ref-ruling> consid. 4). Dès lors que le recours porte exclusivement sur le montant des contributions à l'entretien des enfants, l'on se trouve en présence d'une affaire pécuniaire dont la valeur litigieuse, calculée sur la base de l'<ref-law>, atteint le minimum fixé par la loi pour la recevabilité du recours en matière civile (<ref-law>). La décision attaquée a par ailleurs été prise en dernière instance cantonale et sur recours par le tribunal supérieur du canton de Genève (<ref-law>) et le recourant, qui a pris part à la procédure devant l'autorité précédente et démontre un intérêt juridique à la modification de la décision attaquée (<ref-law>), a agi en temps utile (<ref-law>). Le recours en matière civile est donc en principe recevable, à l'exclusion du recours constitutionnel subsidiaire (<ref-law>).
L'intitulé erroné d'un recours ne nuit pas à son auteur, pour autant que les conditions de recevabilité du recours qui aurait dû être interjeté soient réunies (<ref-ruling> consid. 1.2 p. 382 et les arrêts cités). Le recours constitutionnel subsidiaire du recourant sera dès lors traité comme un recours en matière civile dont les conditions de recevabilité sont remplies.
2. Les mesures protectrices de l'union conjugale sont considérées comme des mesures provisionnelles au sens de l'<ref-law> (<ref-ruling> consid. 5 p. 396, 585 consid. 3.3 p. 587 et la jurisprudence citée), de sorte que seule peut être dénoncée la violation de droits constitutionnels.
3. Constatant les faibles ressources du recourant et afin de respecter le principe d'égalité de traitement entre enfants, les juges cantonaux ont calculé le minimum vital du recourant sans la charge représentée par la contribution d'entretien versée mensuellement à son fils aîné, issu d'un premier lit. Le montant des charges du recourant a ainsi été fixé à 3'693 fr. 90, son solde disponible se chiffrant à 1'130 fr. 10. La cour cantonale en a déduit que le recourant disposait d'une somme suffisante pour s'acquitter du montant des pensions alimentaires fixées par le Tribunal de première instance en faveur de ses deux enfants A._ et B._. Après paiement des contributions de 350 fr. à chacun d'eux, le recourant disposait en effet d'un solde de 430 fr. qu'il pouvait consacrer entièrement ou en partie à l'entretien de son fils aîné C._.
Dans ses observations au présent recours, la Cour de justice a toutefois reconnu avoir fait une erreur de calcul en additionnant les charges du recourant. Elle a pourtant considéré que la baisse de son solde disponible - dont le montant, après correction, se chiffrait à 930 fr. 30 - n'influait pas sur la somme des contributions dues.
4. Saisi d'un recours en matière civile, le Tribunal fédéral applique le droit d'office (<ref-law>) à l'état de fait constaté dans l'arrêt cantonal. Il n'est lié ni par les motifs invoqués par les parties, ni par l'argumentation juridique retenue par l'autorité cantonale (cf. <ref-ruling> consid. 2.2). Il peut donc admettre un recours pour un autre motif que ceux qui ont été invoqués par le recourant, comme il peut le rejeter en adoptant une argumentation différente de celle de l'autorité précédente (cf. <ref-ruling> consid. 2.2; <ref-ruling> consid. 1.4 in fine; 297 consid. 3.1). Dans le cas particulier d'un recours formé contre une décision portant sur une mesure provisionnelle, le Tribunal fédéral dispose cependant d'un pouvoir d'examen limité (<ref-law>). Le Tribunal fédéral ne peut dès lors procéder à une substitution de motifs que pour autant que la nouvelle motivation n'ait pas expressément été réfutée par l'autorité cantonale et qu'elle résiste, à son tour, au grief de violation des droits constitutionnels (<ref-ruling> consid. 4/aa; <ref-ruling> cons. 3c/bb). Il ne fait toutefois usage de cette faculté que si la situation juridique est claire (<ref-ruling> consid. 4d). Ces conditions sont remplies dans le cas présent.
5. Dans la mesure où des enfants sont concernés, le juge ordonne les mesures nécessaires, d'après les effets de la filiation (<ref-law>).
5.1 Aux termes de l'<ref-law>, les père et mère doivent pourvoir à l'entretien de l'enfant et assumer, par conséquent, les frais de son éducation, de sa formation et des mesures prises pour le protéger (al. 1); l'entretien est assuré par les soins et l'éducation ou, lorsque l'enfant n'est pas sous la garde de ses père et mère, par des prestations pécuniaires (al. 2). Selon l'<ref-law>, la contribution d'entretien doit correspondre aux besoins de l'enfant ainsi qu'à la situation et aux ressources des père et mère; il est tenu compte de la fortune et des revenus de l'enfant, ainsi que de la participation de celui des parents qui n'a pas la garde de l'enfant à la prise en charge de ce dernier. Ces différents critères doivent être pris en considération; ils exercent une influence réciproque les uns sur les autres. Ainsi, les besoins de l'enfant doivent être examinés en relation avec les trois autres éléments évoqués et la contribution d'entretien doit toujours être dans un rapport raisonnable avec le niveau de vie et la capacité contributive du débirentier (<ref-ruling> consid. 3a p. 112). En présence de capacités financières limitées, le minimum vital du débirentier au sens du droit des poursuites doit en principe être garanti (<ref-ruling> consis 2c p. 70; <ref-ruling> consid. 1a/aa p. 356; <ref-ruling> consid. 3b/bb p. 5 et consid. 5 p. 9; <ref-ruling> consid. 2 p. 370 ss). En outre, lorsque plusieurs enfants ont droit à une contribution d'entretien, le principe de l'égalité de traitement doit être respecté (<ref-ruling> consid. 2c p. 70; <ref-ruling> consid. 2b p. 357 et les arrêts cités).
5.2 Si les ressources des père et mère sont suffisantes pour couvrir les besoins de l'enfant, il suffit de fixer la part que chacun des parents doit supporter en fonction de sa capacité contributive. En revanche, lorsque les capacités financières du débirentier sont modestes comparativement au nombre d'enfants créanciers d'aliments, il convient de prendre comme point de départ son minimum vital au sens du droit des poursuites, sans les charges représentées par les contributions d'entretien dues à d'autres enfants en vertu d'un jugement de divorce (<ref-ruling> consid. 2c p. 70; arrêts 5A_62/2007 du 24 août 2007 consid. 6.2; 5C.127/2003 du 15 octobre 2003, consid. 4.1.4). Si les moyens financiers du débiteur sont suffisants, son minimum vital pourra être augmenté de certains montants, y compris les impôts; le solde disponible sera ensuite réparti entre les enfants en respectant le principe de l'égalité de traitement. Si ses moyens sont insuffisants, il faut partir de son minimum vital, sans prendre en considération la charge fiscale (ATF <ref-ruling> consid. 1a/aa p. 356), et répartir le disponible selon le principe de l'égalité de traitement. Selon ce principe, les enfants d'un même débiteur doivent être financièrement traités de manière semblable, proportionnellement à leurs besoins objectifs; l'allocation de montants différents n'est donc pas exclue, mais doit avoir une justification particulière (ATF <ref-ruling> consid. 2b p. 357 et les références). Le cas échéant, le débiteur devra ouvrir action en modification du jugement de divorce qui fixe des contributions trop élevées pour certains de ses enfants. Les mêmes principes sont applicables pour l'augmentation des contributions en fonction de l'âge des enfants.
6. 6.1 Le recourant relève que, par leur erreur de calcul, les juges cantonaux auraient fixé des contributions d'entretien qui porteraient atteinte à son minimum vital et que leur décision serait dès lors arbitraire. Afin d'éviter que son minimum vital ne soit entamé, le recourant estime que la cour cantonale devait le condamner à verser un montant de 250 fr. maximum pour A._ et B._, ce afin de lui permettre de s'acquitter de la somme de 430 fr. en faveur de son fils aîné C._. Le recourant conclut néanmoins à ce que le montant des pensions à verser à A._ et B._ soit fixé à 300 fr.
6.2 En tenant compte de la contribution d'entretien en faveur de son fils aîné (750 fr.), les charges du recourant s'élèvent à 4'593 fr. 70 (à savoir: loyer [1'683 fr.]; assurance-maladie [386 fr. 70]; frais de repas [150 fr.]; frais de transport [70 fr.]; impôts [454 fr.]; minimum vital [1'100 fr.]). Les charges de son épouse se chiffrent à 3'529 fr. 10 (à savoir: loyer [1'107 fr.]; assurance-maladie pour elle-même [371 fr. 60]; pour A._ [111 fr.]; pour B._ [111 fr.]; impôts [8 fr. 50]; minimum vital pour elle-même [1'250 fr.]; pour A._ [250 fr.]; pour B._ [250 fr]; frais de transport [70 fr.]). En tant que les salaires respectifs du recourant et de son épouse se montent à 4'824 fr. et 2'700 fr., force est donc de constater que le couple ne dispose pas de revenus suffisants pour faire face à toutes ses charges.
Pour fixer les contributions d'entretien, il convient donc, au vu des principes exposés ci-dessus (consid. 5), de se fonder sur le minimum vital du débirentier, sans toutefois prendre en considération la charge représentée par la contribution d'entretien due à son fils aîné, ni même tenir compte de sa charge fiscale. Il s'ensuit que le disponible du recourant s'élève alors à 1'434 fr. 30. L'épouse bénéficiera ainsi d'un montant de 3'400 fr. pour l'entretien de la famille (2'700 fr. [salaire] + 700 fr. [contributions en faveur des enfants]), alors que ses charges, sans les impôts, se chiffreront à 3'520 fr. 60. L'époux disposera, lui, d'une somme de 4'124 fr. (à savoir 4'824 fr. [salaire] - 700 fr. [contributions à ses deux jeunes enfants]) pour des charges d'un montant de 3'389 fr. 70 (4'593 fr. 70 - 454 fr. [impôts] - 750 [contribution en faveur de C._]). Un solde de 734 fr. 30 restera ainsi à sa disposition pour l'entretien de son fils aîné.
7. Dans un second grief, le recourant demande que, conformément au principe de l'égalité entre enfants, le montant de la contribution d'entretien en faveur de A._ et B._ soit calculé à partir du moment où il était en mesure de réclamer la modification de la contribution d'entretien de son fils C._, à savoir 30 jours après la notification, le 23 octobre 2008, du jugement de première instance.
La péjoration des facultés de paiement du débiteur de la contribution d'entretien peut résulter de la diminution de ses ressources ou de l'augmentation de ses charges du fait, par exemple, de son remariage et/ou de la naissance d'autres enfants. Aux termes de l'<ref-law>, le débirentier peut dès lors demander la modification du montant de la contribution d'entretien (cf. CYRIL HEGNAUER, Commentaire bernois, 1997, n. 73 ad <ref-law>; PETER BREITSCHMID, Commentaire bâlois, 3e éd., 2006, n. 14 ad <ref-law>). En l'occurrence, le recourant devait se rendre compte que, dès la naissance de sa fille, il devrait assumer l'entretien de trois enfants et que, vu ses ressources limitées au regard de ses charges, la contribution fixée en faveur de son fils aîné ne lui permettait pas de faire face à la prise en charge de chacun. Il était dès lors en mesure de réclamer la modification du montant de la pension alimentaire de C._ à ce moment-là déjà, à savoir bien avant que le jugement sur mesures protectrices de l'union conjugale lui soit notifié et le délai de recours échu. Son grief doit en conséquence être rejeté.
8. Vu ce qui précède, le recours doit être rejeté. En tant que les conclusions du recourant n'apparaissaient pas vouées à l'échec et que celui-ci se trouve dans une situation financière délicate (<ref-law>), il y a lieu de donner suite à sa requête d'assistance judiciaire. Celle-ci sera également accordée à l'intimée, qui est indigente. Son conseil lui sera désigné comme avocat d'office et les honoraires de ce dernier seront pris en charge par la Caisse du Tribunal fédéral (<ref-law>). Les frais judiciaires seront mis à la charge du recourant, mais seront toutefois provisoirement supportés par la Caisse du Tribunal fédéral.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours, traité comme un recours en matière civile, est rejeté.
2. La demande d'assistance judiciaire du recourant est admise.
3. La demande d'assistance judiciaire de l'intimée est admise et Me Olivier Lutz lui est désigné comme avocat d'office pour la procédure fédérale.
4. Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant, mais ils sont supportés provisoirement par la Caisse du Tribunal fédéral.
5. La Caisse du Tribunal fédéral versera au conseil de l'intimée une indemnité de 200 fr. à titre d'honoraires.
6. Le présent arrêt est communiqué aux parties et à la Chambre civile de la Cour de justice du canton de Genève.
Lausanne, le 22 juin 2009
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl de Poret