Faits: A. Ressortissante marocaine née le ***1973, X._ serait arrivée en Suisse le 22 mai 1999 au bénéfice d'un visa valable un mois. Elle y serait restée en effectuant de "petits boulots" et aurait rencontré en été 2000 A._, ressortissant macédonien né le ***1968 et titulaire d'une autorisation d'établissement. Ensemble, ils ont eu une fille B._, née le ***octobre 2001. Le 26 novembre 2001, X._ a fait appel à la gendarmerie genevoise en raison de la violence de son compagnon; elle s'est alors vu remettre une carte de sortie avec un délai échéant le 31 décembre 2001. Le 11 décembre 2001, A._ a reconnu B._. Celle-ci, qui vivait alors avec son père, a obtenu une autorisation d'établissement. X._ a épousé A._ le 14 mai 2002 et a, par conséquent, obtenu une autorisation de séjour qui a été régulièrement renouvelée, la dernière fois jusqu'au 13 mai 2005. Par jugement du 16 janvier 2003 sur mesures protectrices de l'union conjugale, les époux AX._ ont été autorisés à vivre séparés. Par mesures préprovisoires du 22 janvier 2004, puis par jugement du 17 juin 2004, l'épouse s'est vu attribuer la jouissance du domicile conjugal ainsi que la garde de B._ et l'époux un droit de visite hebdomadaire, le versement mensuel d'une contribution d'entretien étant mise à la charge de ce dernier. Le 27 juin 2005, l'Office cantonal de la population du canton de Genève (ci-après: l'Office cantonal) s'est prononcé en faveur de la prolongation de l'autorisation de séjour de X._, sous réserve de l'approbation de l'Office fédéral des migrations (ci-après: l'Office fédéral). Par décision du 8 août 2006, l'Office fédéral a refusé d'approuver la prolongation de l'autorisation de séjour de X._ et prononcé son renvoi de Suisse. Le divorce des époux AX._ a été prononcé le 7 décembre 2006 et est entré en force le 27 janvier 2007. B. Par arrêt du 3 février 2009, le Tribunal administratif fédéral a rejeté le recours de X._ contre la décision de l'Office fédéral du 8 août 2006. Il a notamment examiné la cause sous l'angle de l'art. 8 CEDH; il a considéré que la relation de B._ avec son père n'était pas aussi étroite que s'ils vivaient ensemble et que les liens affectifs et économiques les unissant n'étaient pas particulièrement forts. Il a estimé qu'il serait exagéré d'accorder à X._ un droit de présence en Suisse dans le seul but de faciliter l'exercice du droit de visite de A._ sur sa fille. C. Le 12 mars 2009, X._ a déposé un recours en matière de droit public au Tribunal fédéral contre l'arrêt du Tribunal administratif fédéral du 3 février 2009. Elle demande d'annuler l'arrêt attaqué, d'approuver la prolongation de son autorisation de séjour et de celle de son enfant B._, de dire que le renvoi de Suisse ne sera pas ordonné et de renvoyer le dossier à l'autorité inférieure pour nouvelle décision dans le sens des considérants. Elle requiert l'assistance judiciaire. Le Tribunal administratif fédéral a renoncé à se prononcer sur le recours. L'Office fédéral conclut au rejet du recours. L'Office cantonal a produit son dossier à la demande du Tribunal fédéral. D. Par ordonnance du 17 mars 2009, le Président de la IIe Cour de droit public a admis la demande d'effet suspensif contenue dans le recours. 