Faits:
A. Par décision du 7 mars 2011, notifiée le 8 mars 2011, l'Office fédéral des migrations (ci-après: l'Office fédéral) a refusé d'approuver la prolongation de l'autorisation de séjour de A.X._ et a prononcé son renvoi de Suisse.
Par courrier daté du 31 mars 2011 et reçu le 4 avril 2011, A.X._ a transmis à l'Office fédéral une copie de la première page de la décision du 7 mars 2011 et une déclaration de son épouse, B.X._, qu'il a cosignée, selon laquelle le couple faisait à nouveau ménage commun.
Par lettre du 5 avril 2011, l'Office fédéral a indiqué à A.X._ que, comme il ne formulait aucune demande concrète, la décision du 7 mars 2011 restait d'actualité, mais qu'il pouvait encore déposer, le jour-même, un recours auprès du Tribunal administratif fédéral.
Le 13 avril 2011, A.X._ a indiqué à l'Office fédéral qu'il convenait de comprendre le courrier daté du 31 mars 2011 comme une demande de réexamen de la décision du 7 mars 2011 ou comme un recours. L'Office fédéral a transmis l'envoi du 13 avril 2011 au Tribunal administratif fédéral.
B. Par arrêt du 3 mai 2011, le Tribunal administratif fédéral a déclaré irrecevable le recours de A.X._ du 13 avril 2011, parce que déposé tardivement. Quant aux documents remis par A.X._ à l'Office fédéral le 4 avril 2011, les juges ont retenu qu'ils ne pouvaient être considérés comme un recours, puisque la volonté de l'intéressé de contester la décision du 7 mars 2011 ne ressortait pas de ceux-ci.
C. A l'encontre de l'arrêt du 3 mai 2011, A.X._ et B.X._ ont formé un recours en matière de droit public au Tribunal fédéral. Ils concluent à l'annulation de l'arrêt du Tribunal administratif fédéral du 3 mai 2011 et à ce que la cause soit renvoyée à cette autorité pour qu'elle entre en matière sur le recours du 31 mars 2011. Ils demandent également la dispense du paiement des frais de procédure.
Le Tribunal administratif fédéral a renoncé à prendre position sur le recours. L'Office fédéral, se référant aux considérants de l'arrêt attaqué, propose son rejet.
Par ordonnance présidentielle du 15 juillet 2011, la IIe Cour de droit public a admis la demande d'effet suspensif formée ultérieurement par A.X._.

Considérant en droit:
1. 1.1 L'arrêt attaqué est une décision d'irrecevabilité en raison du non-respect du délai de recours, rendue dans une cause de droit des étrangers. Les restrictions à la recevabilité du recours en matière de droit public posées à l'<ref-law> valent aussi s'agissant des décisions procédurales (arrêts 2C_109/2009 du 11 juin 2009 consid. 3; 2C_197/2009 du 28 mai 2009 consid. 6). En tant qu'époux d'une ressortissante suisse (<ref-law>), le recourant dispose d'un droit potentiel à une autorisation de séjour, de sorte que le recours en matière de droit public est ouvert sous l'angle de l'art. 83 let. c ch. 2 LTF (cf. arrêt 2C_376/2010 du 18 août 2010 consid. 2.2.2).
1.2 Au surplus, dirigé contre un arrêt rendu par le Tribunal administratif fédéral (<ref-law>), le recours a été déposé en temps utile (cf. <ref-law>) et dans les formes prescrites (cf. <ref-law>). En outre, A.X._, en tant que destinataire de l'acte attaqué, a indéniablement qualité pour recourir au sens de l'<ref-law>.
On pourrait se demander si l'épouse, B.X._, dès lors qu'elle n'a pas participé à la procédure devant le Tribunal administratif fédéral et ne se plaint pas de n'avoir à tort pas été considérée comme partie, est légitimée à agir. La question peut demeurer indécise, dès lors que, de toute façon, il convient d'entrer en matière sur le recours déposé par son époux.
1.3 Le litige porte exclusivement sur l'arrêt du Tribunal administratif fédéral, qui a qualifié d'irrecevable le recours que lui a transmis l'Office fédéral comme objet de sa compétence. Le recourant ne peut donc s'en prendre, dans le cadre de la présente procédure, au fait que l'Office fédéral n'a pas considéré son courrier du 4 avril 2011 comme une demande de réexamen. Au demeurant, il perd de vue que, dans sa lettre du 13 avril 2011, il a lui-même demandé que ce courrier soit alternativement considéré comme un recours ou comme une demande de réexamen. L'Office fédéral ayant opté pour un recours et transmis la cause au Tribunal administratif fédéral, le litige se limite donc à savoir si c'est à juste titre que ce dernier a considéré que le délai de recours n'avait pas été observé.
2. Invoquant les art. 5 al. 2 et 9 Cst., le recourant reproche au Tribunal administratif fédéral d'avoir fait preuve d'arbitraire, de formalisme excessif et d'avoir admis un comportement de l'Office fédéral contraire au principe de la bonne foi.
2.1 A l'encontre des décisions de l'Office fédéral, un recours au Tribunal administratif fédéral est en principe ouvert (cf. art. 33 let. d LTAF). En vertu de l'<ref-law>, le recours doit être déposé dans les 30 jours qui suivent la notification de la décision. Selon l'<ref-law>, le mémoire de recours doit indiquer les conclusions, motifs et moyens de preuve et porter la signature du recourant ou de son mandataire; celui-ci y joint l'expédition de la décision attaquée et les pièces invoquées comme moyens de preuve, lorsqu'elles se trouvent en ses mains. L'<ref-law> prévoit que si le recours ne satisfait pas à ces exigences, ou si les conclusions ou les motifs du recourant n'ont pas la clarté nécessaire, sans que le recours soit manifestement irrecevable, l'autorité de recours impartit au recourant un court délai supplémentaire pour régulariser le recours. Lorsque le recours est interjeté par un particulier qui ne dispose pas de formation juridique, il convient de ne pas se montrer trop strict dans l'appréciation des conditions formelles posées à l'<ref-law> (cf. ANDRÉ MOSER, Kommentar zum Bundesgesetz über das Verwaltungsverfahren, Zurich 2008, N 1 ad <ref-law>). La jurisprudence admet que l'autorité peut être tenue d'octroyer un délai pour compléter le recours en application de l'<ref-law> même dans des cas où l'écriture présentée ne comporte ni conclusion ni motivation suffisantes. Il ne faut toutefois pas en déduire pour autant qu'un mémoire de recours ne doive répondre à aucune exigence formelle minimale et qu'un délai supplémentaire pour le compléter doive toujours être accordé. En effet, lorsqu'il dépose un recours, le justiciable est tenu d'y apporter un soin minimal. Ainsi, une écriture, pour être qualifiée de recours - même insuffisamment motivé - au sens de l'<ref-law>, avec les effets juridiques qui y sont assortis (suspension de l'entrée en force de la décision attaquée et de son exécution; cf. <ref-law>) doit au moins exprimer de manière reconnaissable que son auteur a la volonté de recourir pour obtenir la modification d'une situation juridique déterminée résultant d'une décision qui le concerne (<ref-ruling> consid. 2b p. 636; <ref-ruling> consid. 5c p. 131, confirmés en relation avec l'<ref-law> in <ref-ruling> consid. 2 p. 163). L'irrecevabilité sanctionnant une écriture qui ne comporte ni motivation ni conclusions ne consacre par ailleurs aucun formalisme excessif, s'agissant d'éléments indispensables pour que l'autorité de recours puisse savoir ce que le recourant reproche à la décision attaquée et ce qu'il veut (arrêt 1P.141/2004 du 10 mai 2004 consid. 2, in: RDAF 2005 I 58, et la référence citée).
2.2 En l'espèce, la décision de l'Office fédéral du 7 mars 2011 a été notifiée au recourant le lendemain, soit le 8 mars 2011, de sorte que le délai de recours de 30 jours de l'<ref-law>, calculé conformément aux articles 20 ss PA, est arrivé à expiration le 7 avril 2011. Ainsi que l'a retenu l'arrêt attaqué, l'écriture du recourant du 13 avril 2011 a donc été déposée tardivement, celui-ci ne prétendant par ailleurs nullement avoir été empêché sans sa faute d'agir dans le délai fixé au sens de l'<ref-law>.
2.3 Reste le point de savoir si, comme le soutient le recourant, son envoi daté du 31 mars 2011 et reçu par l'Office fédéral le 4 avril 2011, aurait dû être considéré comme un recours valable au sens de l'<ref-law> et qu'en ne l'admettant pas, le Tribunal administratif fédéral serait tombé dans l'arbitraire et aurait fait preuve de formalisme excessif.
Il ressort de l'arrêt attaqué que ce courrier comprenait la première page de la décision du 7 mars 2011 et une attestation de l'épouse du recourant selon laquelle celle-ci aurait repris la vie commune, l'époux s'étant contenté de cosigner cette déclaration. Ce document ne contenant aucune explication, ni aucune déclaration de l'intéressé lui-même, l'arrêt attaqué pouvait retenir, sans arbitraire (sur cette notion, cf. <ref-ruling> consid. 2.4 p. 5; <ref-ruling> consid. 3.1 p. 153, et les arrêts cités), que la volonté de recourir ne ressortait pas de ce document. Le recourant n'invoque du reste aucun élément propre à faire apparaître comme insoutenable cette conclusion. Ainsi, ce n'est pas parce que celui-ci s'était opposé, le 18 janvier 2011, au non-renouvellement de son autorisation de séjour, ce qui a amené l'Office fédéral a rendre la décision du 7 mars 2011, qu'il entendait automatiquement recourir contre cette dernière. Contrairement à ce que soutient le recourant, l'<ref-law> ne saurait imposer à l'autorité de déduire elle-même l'intention de recourir de tout document envoyé par un justiciable qui a lui-même négligé de fournir la moindre explication à son appui, ce qui est précisément le cas en l'occurrence.
Ayant retenu sans arbitraire que le courrier du 31 mars 2011 reçu le 4 avril suivant n'exprimait pas de volonté de recourir, le Tribunal administratif fédéral pouvait, sans tomber dans le formalisme excessif (cf. supra consid. 2.1 in fine; pour cette dernière notion, cf. <ref-ruling> consid. 2.1 p. 9; arrêt 2C_373/2011 du 7 septembre 2011 consid. 6.1), considérer que ce document ne remplissait pas les exigences minimales pour pouvoir être qualifié de recours au sens de l'<ref-law>.
2.4 Le recourant reproche encore au Tribunal administratif de ne pas avoir retenu que l'Office fédéral aurait agi contrairement au principe de la bonne foi en classant sans autre son envoi du 31 mars 2011, sans même prendre la peine de l'interroger sur le sens de celui-ci.
Découlant directement de l'art. 9 Cst. et valant pour l'ensemble de l'activité étatique, le droit à la protection de la bonne foi suppose, entre autres conditions, que le justiciable ait été incité à prendre des dispositions préjudiciables à ses intérêts à la suite de décisions, de déclarations ou d'un comportement déterminé de l'administration (cf. <ref-ruling> consid. 2.5.1 p. 72 s.; <ref-ruling> consid. 6.1 p. 636 s. et les arrêts cités).
En l'occurrence, le grief du recourant confine à la témérité. En effet, celui-ci perd de vue que l'Office fédéral, après avoir reçu son envoi daté du 31 mars 2011 le 4 avril, l'a immédiatement avisé, par courrier du 5 avril 2011, qu'il pouvait encore déposer le jour-même un recours auprès du Tribunal administratif fédéral si son intention était de contester la décision du 7 mars 2011. Dans un tel contexte, on ne voit pas que l'on puisse reprocher à l'Office fédéral d'avoir adopté un comportement laissant croire au recourant, contrairement au principe de la bonne foi, que son envoi remplissait les exigences de l'<ref-law> et qu'il pouvait se dispenser de déposer une déclaration de recours dans le délai de 30 jours à partir de la décision du 7 mars 2011.
3. Il découle de ce qui précède que le recours, entièrement mal fondé, doit être rejeté, dans la mesure de sa recevabilité.
La cause étant d'emblée dépourvue de chances de succès, la demande d'assistance judiciaire doit aussi être rejetée (cf. <ref-law>).
Succombant, les recourants supporteront donc les frais judiciaires, solidairement entre eux (art. 65 et 66 al. 1 et 5 LTF), et n'ont pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge des recourants, solidairement entre eux.
4. Le présent arrêt est communiqué aux recourants, à l'Office fédéral des migrations et au Tribunal administratif fédéral, Cour III.
Lausanne, le 4 novembre 2011
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
Le Greffier: Chatton