Faits:
A. A.X._, ressortissant marocain, né en 1984, a été arrêté à Genève au mois de janvier 2005, alors qu'il venait d'Annemasse et était dépourvu de papier d'identité. Jusqu'à son mariage avec une ressortissante suisse, B._, le 2 juin 2008, il s'est légitimé sous le nom de Y._, ressortissant algérien, né en 1987. Avant son mariage, il a été condamné à onze reprises, principalement pour infractions à la loi fédérale sur le séjour et l'établissement des étrangers (aLSEE) et à la loi fédérale sur les stupéfiants (LStup), à des peines totalisant 344 jours d'emprisonnement. Il a également fait l'objet de deux décisions d'interdiction d'entrée en Suisse de la part de l'Office fédéral des migrations: le 10 février 2005, pour une durée de trois ans et le 22 mai 2007, pour la période du 10 février 2008 au 21 mai 2017.
Le 30 juin 2008, A.X._ et son épouse B._ ont présenté une demande d'autorisation de séjour pour regroupement familial. A.X._ a encore été condamné, le 28 août 2008, à une peine privative de liberté de 60 jours pour infractions à la LStup et, le 17 septembre 2009, à une peine pécuniaire de 90 jours-amende à 30 fr. pour violence ou menace contre les autorités et les fonctionnaires.
B. Le 27 juillet 2009, l'Office fédéral des migrations a indiqué à A.X._ qu'il entendait refuser de lever l'interdiction d'entrée en Suisse prononcée à l'encontre de ce dernier et lui a donné l'occasion de se déterminer. L'intéressé n'a toutefois émis aucune observation à cet égard.
Par décision du 21 décembre 2009, l'Office fédéral des migrations a refusé d'approuver l'octroi d'une autorisation de séjour à A.X._. Il a également prononcé son renvoi de Suisse et a refusé de procéder au réexamen de la décision d'interdiction d'entrée du 22 mai 2007.
Le 1er février 2010, A.X._ et B.X._ ont recouru contre cette décision auprès du Tribunal administratif fédéral.
Par ordonnance du 1er juillet 2011, le Ministère public genevois a reconnu A.X._ coupable de vol d'usage d'un véhicule et de circulation sans permis de conduire et l'a condamné à un travail d'intérêt général de 60 heures, ainsi qu'à une amende de 100 fr.
Le 24 mai 2012, les époux X._ ont été arrêtés par la police genevoise. A leur domicile, la police a notamment découvert 29,7 gr d'héroïne, 2,9 gr de marijuana, 0,6 gr de haschich, des cartouches de munitions et une centaine de sachets de minigrip vides. Le procès-verbal d'audition de A.X._ du 24 mai 2012 et le rapport de police du 25 mai 2012, établis à cette occasion, ont été transmis au Tribunal administratif fédéral le 8 juin 2012.
Dans le délai au 15 juin 2012 qui lui avait été imparti pour se déterminer sur les observations complémentaires de l'Office fédéral des migrations, le mandataire de A.X._ a déposé un bon pour une consultation médicale de son client aux HUG.
C. Par arrêt du 28 septembre 2012, le Tribunal administratif fédéral a rejeté le recours. Laissant ouverte la question de la qualité pour agir de l'épouse, il a retenu en bref que si le recourant n'avait été frappé d'aucune peine de longue durée, il avait néanmoins été condamné à quinze reprises par les autorités judiciaires genevoises et avait fait usage d'une fausse identité pendant plusieurs années. La répétition et la constance de ses actes délictueux, encore vérifiées lors de son arrestation au mois de mai 2012, démontraient son incapacité à se conformer au droit en vigueur. Par ailleurs, l'intérêt public à éloigner A.X._ l'emportait sur son intérêt privé et celui de son épouse à pouvoir vivre ensemble en Suisse. Le Tribunal a aussi estimé proportionné le maintien de la mesure d'interdiction prononcée par l'Office fédéral des migrations jusqu'au 21 mai 2017. Il a accordé l'assistance judiciaire au recourant.
D. Agissant par la voie du recours en matière de droit public, A.X._ et B.X._ concluent à l'annulation de l'arrêt du Tribunal administratif fédéral en tant qu'il rejette leur recours et à l'approbation de l'octroi d'une autorisation de séjour en faveur du recourant. Ils demandent aussi la levée de l'interdiction d'entrée prise à l'encontre de A.X._ et présentent une demande d'assistance judiciaire.
Au terme de ses observations, le Tribunal administratif fédéral conclut au rejet du recours. Il a également transmis au Tribunal fédéral la demande de réexamen que lui a adressée B.X._ les 24 et 26 octobre 2012, avec les pièces qui l'accompagnaient, l'échange de correspondances qu'il a eu avec celle-ci au mois de février 2013, ainsi qu'une lettre de l'intéressée du 22 mars 2013.
De son côté, l'Office fédéral des migrations propose de rejeter le recours.
E. Par ordonnance présidentielle du 6 novembre 2012, l'effet suspensif a été attribué au recours.

Considérant en droit:
1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit.
1.1 Selon l'art. 42 al. 1 de la loi fédérale sur les étrangers (LEtr; RS 142.20), le conjoint d'un ressortissant suisse a droit à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité à condition de vivre en ménage commun avec lui. Par ailleurs l'art. 8 CEDH, dont se prévalent les recourants sous l'angle de la protection de la vie familiale, peut être invoqué par l'étranger pour s'opposer à la séparation de sa famille, lorsque sa relation avec une personne ayant le droit de résider durablement en Suisse est étroite et effective (<ref-ruling> consid. 1.3 p. 287). Il est en l'espèce constant que le recourant habite avec son épouse, de nationalité Suisse, depuis son mariage en juin 2008. Potentiellement, il peut donc prétendre à une autorisation de séjour. La question de savoir s'il a effectivement droit à l'octroi d'une telle autorisation sur la base des dispositions précitées relève du fond et non de la recevabilité (consid. 2.1.2 non publié de l'<ref-ruling>; arrêt 2C_618/2009 du 27 janvier 2010 consid. 2.2). Par conséquent, le recours est recevable sous l'angle de l'art. 83 let. c ch. 2 LTF.
1.2 En tant que destinataire de l'arrêt attaqué, le recourant a qualité pour recourir au sens de l'<ref-law>. Cette qualité doit être également reconnue à la recourante qui a un intérêt digne de protection à l'annulation ou à la modification de l'arrêt entrepris au sens de cette disposition, dans la mesure où elle peut se prévaloir de l'art. 8 § 1 CEDH, respectivement 13 al. 1 Cst., afin de pouvoir poursuivre sa vie conjugale en Suisse.
1.3 Au surplus, déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (<ref-law>), le présent recours, dirigé contre une décision du Tribunal administratif fédéral (<ref-law>), est recevable comme recours en matière de droit public en tant qu'il porte sur l'octroi d'une autorisation de séjour au recourant. Il est en revanche irrecevable, en vertu de l'art. 83 let. c ch. 1 LTF, en tant qu'il conclut à la levée de l'interdiction d'entrer en Suisse prononcée à l'encontre de ce dernier. L'autorité judiciaire de dernière instance étant une autorité judiciaire fédérale, le recours de droit constitutionnel subsidiaire est également exclu sur ce point (<ref-law> a contrario).
2. Les recourants invoquent une violation de leur droit d'être entendu, plus particulièrement de leur droit à pouvoir se déterminer sur le rapport de police du 25 mai 2012 et le procès-verbal d'audition du 24 mai 2012, versés au dossier le 8 juin 2012, dont le Tribunal fédéral administratif s'est prévalu pour évaluer le risque de récidive du recourant et sa dépendance à l'héroïne.
2.1 Ce grief doit être examiné en premier lieu. En effet, compte tenu du caractère formel du droit d'être entendu, si la violation devait être avérée, elle entraînerait l'annulation de l'arrêt attaqué quelles que soient les chances de succès du recours sur le fond (<ref-ruling> consid. 2.2 p. 197; <ref-ruling> consid. 2.6.1 p. 285).
2.2 Le droit d'être entendu garanti par l'art. 29 al. 2 Cst. n'oblige pas en tous les cas l'autorité à renseigner les parties sur chaque production de pièces; il peut suffire, selon les circonstances, que celle-ci tienne le dossier à leur disposition (<ref-ruling> consid. 2a p. 202; arrêts 1C_153/2009 du 3 décembre 2009, consid. 2.2). Toutefois, l'autorité qui verse au dossier de nouvelles pièces, que le recourant ne connaît pas et ne pouvait pas connaître, et dont elle entend se prévaloir dans son jugement, est tenue d'en aviser les parties (<ref-ruling> consid. 3.1 p. 388 et consid. 6.2 p. 391; <ref-ruling> consid. 2b p. 137; <ref-ruling> consid. 2a p. 202; arrêt 2C_341/2008 du 30 octobre 2008, consid. 5.1), sans égard au fait de savoir si ces pièces sont de nature à influer effectivement sur le sort de la cause (<ref-ruling> consid. 3.2 p. 389; arrêts 1C_214/2012 du 4 décembre 2012, consid. 2.1 et 1C_88/2011 du 15 juin 2011, consid. 3.4).
2.3 En l'espèce, il n'est pas contesté que la dernière communication du Tribunal fédéral administratif au mandataire du recourant, avant l'arrêt attaqué, date du 16 mai 2012. Un délai d'un mois était alors fixé à celui-ci pour se déterminer sur les observations de l'autorité inférieure. Le rapport de police et le procès-verbal d'audition en cause, transmis le 8 juin 2012 à l'autorité judiciaire fédérale par l'Office cantonal de la population du canton de Genève, n'ont donc pas été envoyés pour information au mandataire du recourant, ni signalés à ce dernier comme étant versés au dossier. L'autorité inférieure n'en a pas non plus eu connaissance lorsqu'elle a produit ses observations finales. Or, les pièces en cause n'étaient pas sans importance, dans la mesure où le Tribunal administratif fédéral s'y est référé dans l'arrêt attaqué et a estimé que les condamnations subies par l'intéressé, dont la plus importante était de 90 jours, ne constituaient pas un motif de révocation de l'autorisation de séjour, a fortiori de refus d'octroi de cette autorisation, mais qu'il y avait lieu de tenir compte de la persistance du recourant dans son activité délictueuse et du fait qu'aucun pronostic favorable ne pouvait être posé, en l'état, sur son comportement. Ce faisant, il s'est clairement basé sur le rapport de renseignements de la police genevoise du 25 mai 2012 et sur le procès-verbal d'audition du recourant du 24 mai 2012. Il a ainsi souligné la constance de l'activité délictuelle du recourant, plus particulièrement en matière de stupéfiants " qui s'est encore vérifiée lors de son arrestation du mois de mai 2012, dans le cadre de laquelle il a notamment été trouvé en possession de 1,1 gramme d'héroïne et a admis pratiquer la revente de cette substance " (cf. arrêt attaqué consid. 7.1).
Au sujet du grief formel, la juridiction inférieure allègue que le recourant est de mauvaise foi lorsqu'il prétend avoir ignoré l'existence des pièces en cause et qu'il devait se douter que celles-ci pouvaient être communiquées à l'instance chargée d'instruire son recours. En tout état de cause, il lui appartenait de venir consulter son dossier devant le Tribunal administratif fédéral. Cette argumentation ne saurait être retenue s'agissant de pièces produites après les observations finales de l'Office fédéral des migrations, qui étaient déterminantes pour se prononcer sur la proportionnalité de la mesure d'éloignement du recourant par rapport à l'intérêt public en jeu. La question n'est donc pas de savoir si le recourant connaissait ou non le contenu de ces pièces, puisqu'il ne savait même pas que celles-ci avaient été versées au dossier et qu'il ne pouvait pas se douter qu'il en serait fait état dans le jugement entrepris. Dès lors que le Tribunal administratif fédéral entendait se prévaloir de ces documents, il aurait dû au moins avertir le mandataire des recourants que ces pièces avaient été produites et figuraient au dossier. Le fait que ces éléments ne constituaient que des indices supplémentaires dans la longue liste des agissements délictueux du recourant et n'étaient ainsi, à eux seuls, pas déterminants ne le dispensait pas de cette obligation. Partant, l'absence de communication du rapport de police et du procès-verbal d'audition en cause constitue bien une violation du droit d'être entendu des recourants.
2.4 Ce vice ne pouvant pas être réparé devant le Tribunal fédéral (cf. <ref-ruling> consid. 2.7 p. 199; arrêts 2C_560/2012 du 23 janvier 2013, consid. 4.6; 5A_535/2012 du 6 décembre 2012 consid. 3), il entraîne l'admission du recours dans la mesure de sa recevabilité. L'arrêt attaqué doit dès lors être annulé et la cause renvoyée au Tribunal administratif fédéral pour qu'il donne l'occasion aux recourants de se déterminer sur les pièces reçues le 8 juin 2012 avant de statuer à nouveau.
3. Au vu de l'issue du litige, il n'y pas lieu de percevoir des frais judiciaires (<ref-law>). Des dépens seront alloués au recourant (<ref-law>). Dès lors que le Tribunal administratif fédéral est à l'origine des frais inutiles occasionnés à celui-ci, il y a lieu de le condamner aux dépens (cf. art. 66 al. 3 par renvoi de l'<ref-law>; THOMAS GEISER, Bundesgerichtsgesetz, Commentaire bâlois, 2e édition, Bâle 2011, n. 17 s. ad art 68; BERNARD CORBOZ, Commentaire LTF, Berne 2009, n. 44 ad art. 68). Par conséquent, la demande d'assistance judiciaire présentée par les recourants devient sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis dans la mesure où il est recevable. L'arrêt attaqué est annulé et la cause renvoyée au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Le Tribunal administratif fédéral versera au mandataire des recourants une indemnité de 2'000 fr. à titre de dépens.
4. Le présent arrêt est communiqué au mandataire des recourants, à l'Office fédéral des migrations et au Tribunal administratif fédéral, Cour III, ainsi qu'à l'Office cantonal de la population du canton de Genève.
Lausanne, le 26 avril 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Rochat