Faits:
A. Née le 10 juin 1972, X._ est ressortissante du Sri Lanka.
Le 9 mars 2012, elle a fait l'objet d'une décision de renvoi de la part de l'Office fédéral des migrations (ci-après: l'Office fédéral) à la suite d'un refus d'asile. Elle a recouru contre cette décision, recours que le Tribunal administratif fédéral a rejeté par arrêt du 18 juillet 2012.
B. Par arrêt du 7 février 2013, le Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Juge unique), après avoir auditionné l'intéressée, a approuvé la décision rendue le 5 janvier 2013 par le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) ordonnant la mise en détention immédiate en vue du renvoi, pour trois mois au plus, de X._.
C. A l'encontre de l'arrêt du 7 février 2013, X._ forme, en langue allemande, un recours en matière de droit public au Tribunal fédéral, en concluant à l'annulation de l'arrêt attaqué et à sa remise en liberté. Elle sollicite en outre le bénéfice de l'assistance judiciaire et la nomination de Me Gabriel Püntener, avocat à Berne, en qualité d'avocat d'office.
Le Service cantonal a transmis son dossier sans observations. Le Tribunal cantonal du canton du Valais a également renoncé à se déterminer.

Considérant en droit:
1. 1.1 En matière de mesures de contrainte, la décision rendue en dernière instance cantonale par le Juge unique peut faire l'objet d'un recours en matière de droit public au Tribunal fédéral (cf. arrêt 2C_142/2013 du 1er mars 2013 consid. 1). Interjeté en temps utile (<ref-law>) et dans les formes requises (<ref-law>) par la recourante qui se trouve en détention administrative et remplit partant les conditions de l'<ref-law>, le présent recours est en principe recevable.
1.2 D'après l'<ref-law>, les mémoires de recours doivent être rédigés dans une langue officielle. Selon l'<ref-law>, la procédure devant le Tribunal fédéral est conduite dans l'une des langues officielles (allemand, français, italien, rumantsch grischun), en règle générale dans la langue de la décision attaquée. Le recourant peut rédiger le mémoire de recours dans la langue (officielle) de son choix, qui ne doit pas nécessairement correspondre à celle de la procédure devant le Tribunal de céans (arrêt 2C_386/2012 du 16 novembre 2012 consid. 1 et les références citées).
En l'occurrence, la recourante a déposé un recours en langue allemande. Ainsi qu'il vient d'être dit, ce procédé est admissible. La langue de la procédure est toutefois le français et le présent jugement sera rendu dans cette langue.
2. Le Tribunal fédéral est un juge du droit. Il doit vérifier si, sur la base des faits constatés par l'instance inférieure, le droit a été correctement appliqué (cf. arrêt 2C_142/2013 du 1er mars 2013 consid. 3 et les références citées). L'examen du Tribunal fédéral se fonde donc sur les faits constatés par l'autorité précédente (cf. <ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire (cf. <ref-ruling> consid. 4.1.2 p. 62; cf. pour la notion d'arbitraire <ref-ruling> consid. 7.1 p. 51) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). 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>). En matière de détention administrative, les éléments nouveaux de nature à confirmer ou infirmer l'imminence de l'exécution du renvoi qui sont transmis au Tribunal fédéral par les autorités peuvent être pris en compte en application de l'<ref-law> dans la seule mesure où ils sont pertinents pour apprécier le bien-fondé du maintien de l'étranger en détention (cf. arrêts 2C_142/2013 du 1er mars 2013 consid. 3; 2C_1017/2012 du 30 octobre 2012 consid. 2).
En l'occurrence, la recourante n'invoque pas que les faits auraient été constatés de façon manifestement inexacte ou arbitraire. Partant, la Cour de céans appréciera le bien-fondé de la détention administrative contestée sur la base des seuls éléments de fait ressortant de l'arrêt attaqué.
3. Se fondant sur l'art. 76 al. 1 let. b ch. 3 et 4 LEtr, l'arrêt attaqué considère en substance que la mise en détention en vue du renvoi de la recourante est justifiée, en raison des contradictions contenues dans ses déclarations, qui dénotent qu'elle se préoccupe assez peu de la crédibilité de ses dires dans les procédures officielles. Selon l'arrêt attaqué, la recourante a en effet affirmé à l'audience du 7 février 2013 que ses parents lui avaient appris, après son interrogatoire du 17 novembre 2009 sur ses motifs d'asile, que sa fille, née en 1989, avait disparu en 2009 pendant une guerre, alors qu'au cours de cet interrogatoire, elle avait indiqué que son enfant avait été emmenée par un inconnu. Par ailleurs, l'existence d'une nouvelle procédure d'asile ne suffisait pas à elle seule à modifier un renvoi, dont la légalité n'avait au surplus pas à être examinée dans la procédure de détention administrative.
4. Dans un grief formel qu'il convient d'examiner en premier lieu, la recourante se plaint d'une violation de l'art. 29 al. 2 Cst., soutenant que l'arrêt attaqué ne contient pas de motivation permettant de justifier sa détention.
Le droit d'être entendu (art. 29 al. 2 Cst.) est respecté, selon la jurisprudence, si l'autorité mentionne, au moins brièvement, les motifs qui l'ont guidée et sur lesquels elle a fondé sa décision, de manière à ce que l'intéressé puisse se rendre compte de la portée de celle-ci et l'attaquer en connaissance de cause (cf. <ref-ruling> consid. 5.2 p. 236).
En l'espèce, contrairement à ce que soutient la recourante, l'arrêt attaqué permet de comprendre les motifs qui ont conduit le Juge unique à confirmer la mise en détention de cette dernière, ce qui exclut une violation de l'art. 29 al. 2 Cst. Le grief est donc infondé. Quant à savoir si ces motifs sont suffisants pour justifier cette détention, il s'agit d'une question de fond qu'il convient d'examiner sous cet angle. Du reste, la recourante se plaint aussi de l'absence de motif de détention.
5. 5.1 La détention administrative porte une atteinte grave à la liberté personnelle et suppose en particulier qu'elle respecte le principe de la légalité (cf. arrêts 2C_40/2013 du 7 mars 2013 consid. 4.2; 2C_1139/2012 du 21 décembre 2012 consid. 3.1). Cela implique que la mise en détention administrative ne soit prononcée que si les motifs prévus dans la loi sont concrètement réalisés (arrêt 2C_478/2012 du 14 juin 2012 consid. 2.1). L'art. 76 al. 1 let. b ch. 3 et 4 LEtr sur lequel se fonde le Juge unique prévoit que, lorsqu'une décision de renvoi a été notifiée, l'autorité compétente peut, afin d'en assurer l'exécution, mettre en détention la personne concernée si des éléments concrets font craindre qu'elle entend se soustraire au renvoi ou à l'expulsion, en particulier parce qu'elle ne se soumet pas à son obligation de collaborer (cf. ch. 3), ou si son comportement permet de conclure qu'elle se refuse à obtempérer aux instructions des autorités (cf. ch. 4). Selon la jurisprudence, ces motifs sont réalisés en particulier lorsque l'étranger tente d'entraver les démarches en vue de l'exécution du renvoi en donnant des indications manifestement inexactes ou contradictoires ou encore s'il laisse clairement apparaître, par ses déclarations ou son comportement, qu'il n'est pas disposé à retourner dans son pays d'origine (cf. <ref-ruling> consid. 3.1 p. 58 s.; arrêt 2C_1139/2012 du 21 décembre 2012 consid. 3.2). Il faut qu'il existe des éléments concrets en ce sens (cf. arrêt 2C_1017/2012 du 30 octobre 2012 consid. 4.1.1 et les références citées).
Le seul fait de ne pas quitter le pays dans le délai imparti à cet effet ne saurait suffire, pris individuellement, à admettre un motif de détention (cf. arrêt 2C_142/2013 du 1er mars consid. 4.2 in fine). En outre, pour justifier une détention sur la base de l'art. 76 al. 1 ch. 3 et 4 LEtr, n'importe quelle contradiction dans les propos de l'étranger ne suffit pas. Il faut que les indications contradictoires soient en lien avec le risque que l'intéressé se soustraie à son renvoi et refuse d'obtempérer aux injonctions des autorités. La Cour de céans a déjà indiqué à de multiples reprises au Juge unique valaisan que le fait que le recourant varie sur la composition de sa famille n'était pas propre à fonder une mise en détention administrative (cf. arrêts 2C_142/2013 du 1er mars 2013 consid. 4.4; 2C_420/2011 du 9 juin 2011 consid. 3.2; 2C_963/2010 du 11 janvier 2011 consid. 2.2; 2C_945/2010 du 5 janvier consid. 2.2).
5.2 En l'espèce, l'arrêt attaqué fonde la détention exclusivement sur les propos contradictoires qu'aurait tenus la recourante quant à la disparition de sa fille. On peine cependant à comprendre quelle est le lien entre les motifs de la disparition de la fille de la recourante en 2009 et la mise en détention de cette dernière. Le fait que la recourante ait d'abord prétendu que sa fille avait été emmenée par un inconnu, puis qu'elle ait soutenu que ses parents lui avaient appris par la suite que l'enfant avait disparu pendant une guerre, n'est du reste pas véritablement contradictoire. Quoi qu'il en soit, peu importe, dès lors que le fait que la recourante ait varié dans ses explications à ce sujet ne permet pas, contrairement à ce que retient l'arrêt attaqué, d'en déduire un indice concret qu'elle risquerait de ne pas obtempérer aux injonctions des autorités et de partir dans la clandestinité. Il appartenait au Juge unique de mettre en évidence d'autres éléments tangibles en ce sens, ce qu'il n'a pas fait.
Le seul motif retenu dans la décision attaquée est donc manifestement impropre à fonder une détention administrative en application de l'art. 76 al. 1 ch. 3 et 4 LEtr. La détention de la recourante est donc illégale, ce qui justifie de la libérer.
6. 6.1 Au vu de ce qui précède, le recours doit être admis et l'arrêt attaqué annulé, ce qui entraîne le prononcé de la libération immédiate de la recourante.
6.2 Bien qu'il succombe, le canton du Valais n'a pas à supporter de frais judiciaires (cf. <ref-law>); il y a lieu de souligner que l'on se trouve dans un cas limite où l'insuffisance claire des motifs à l'appui de la détention, qui a déjà été sanctionnée à plusieurs reprises par le Tribunal fédéral (cf. supra consid. 5), aurait pu justifier de mettre les frais à la charge du canton du Valais. En effet, la collectivité publique dont dépend l'autorité intimée peut exceptionnellement être amenée à assumer les frais judiciaires, en particulier lorsque l'autorité a commis une violation qualifiée du devoir de rendre la justice (cf. arrêts 4A_518/2012 du 8 janvier 2013 consid. 3.1 et les références citées; I 1096/06 du 24 juillet 2007 consid. 5; BERNARD CORBOZ, in CORBOZ/ WURZBURGER/FERRARI/FRÉSARD/AUBRY GIRARDIN, Commentaire de la LTF, 2009, n° 22 ad <ref-law>; THOMAS GEISER, in Niggli/Uebersax/ Wiprächtiger (éd.), Basler Kommentar zum BGG, 2e éd. 2011, n° 30 ad <ref-law>).
Le canton du Valais supportera en revanche les dépens alloués à la recourante, représentée par un avocat et qui obtient gain de cause (cf. <ref-law>). Ceux-ci seront fixés par le Tribunal fédéral d'après le dossier, conformément au règlement du 31 mars 2006 sur les dépens alloués à la partie adverse et sur l'indemnité pour la représentation d'office dans les causes portées devant le Tribunal fédéral (RS 173.110.210.3), dès lors que les frais et dépens que le mandataire de la recourante fait valoir à la fin du mémoire de recours ne correspondent pas à un état de frais au sens de l'art. 12 al. 2 dudit règlement.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'arrêt du 7 février 2013 est annulé.
2. La recourante est immédiatement libérée.
3. Il n'est pas perçu de frais.
4. Le canton du Valais versera à la recourante une indemnité de CHF 2'000.- à titre de dépens.
5. Le présent arrêt est communiqué au mandataire de la recourante, au Service de la population et des migrations du canton du Valais, au Juge unique de la Cour de droit public du Tribunal cantonal du canton du Valais et à l'Office fédéral des migrations.
Lausanne, le 27 mars 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Beti