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._. 