Faits:
A. A.X._, ressortissant algérien né en 1965, est arrivé en Suisse le 2 avril 2002. Il a déposé une demande d'asile qui lui a été refusée par décision du 13 août 2002 de l'Office fédéral des réfugiés. Cette décision a été confirmée sur recours par la Commission de recours en matière d'asile. Un délai de départ a été fixé à A.X._ au 21 mai 2003.
L'intéressé a été condamné à plusieurs reprises pour diverses infractions pénales aux peines suivantes:
- cinq jours d'emprisonnement avec sursis durant deux ans pour appropriation illégitime, utilisation frauduleuse d'un ordinateur et défaut d'avis en cas de trouvaille (ordonnance pénale du 10 juin 2002 du Ministère public du canton de Neuchâtel);
- cinq jours d'arrêt avec sursis pendant un an pour vol d'importance mineur (ordonnance pénale du 21 juin 2002 du Ministère public du canton ce Neuchâtel);
- douze mois d'emprisonnement pour vols, recel et défaut d'avis en cas de trouvaille (jugement du 24 janvier 2006 du Bezirkgericht Zurich);
- trois mois d'emprisonnement pour infraction aux dispositions sur le séjour des étrangers et expulsion du territoire suisse pour une durée de trois ans en raison de désobéissance à la police (jugement du 26 septembre 2006 du Tribunal de police du district de La Chaux-de-Fonds);
- 440 heures de travail d'intérêt général, sous déduction de 21 jours de détention avant jugement pour vol, vol d'importance mineure, dénonciation calomnieuse et infraction aux dispositions sur le séjour des étrangers (jugement du 26 janvier 2009 du Tribunal correctionnel de l'arrondissement de l'Est vaudois et arrêt du 6 juillet 2009 de la Cour de cassation pénale);
- 480 heures de travail d'intérêt général pour vol, violation graves des règles de la circulation routière et séjour illégal (jugement du 28 septembre 2009 du Tribunal de police du district de Neuchâtel).
Le 25 août 2008, A.X._ a épousé, à Boudry, B._, détentrice d'une autorisation d'établissement. Il a demandé l'octroi d'une autorisation de séjour par regroupement familial.
Par la suite, A.X._ a fait l'objet de plusieurs rapports de police pour vols.
B. Par décision du 11 février 2009, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) a rejeté la demande d'autorisation de séjour au motif que A.X._ avait été condamné à plusieurs reprises essentiellement pour vol. Cette décision a été assortie de l'obligation de quitter le territoire neuchâtelois sans délai.
Le 13 mars 2009, les époux ont interjeté recours contre la décision du Service des migrations devant le Département de l'économie du canton de Neuchâtel (ci-après: le Département de l'économie). Ils estimaient qu'il n'avait pas suffisamment été tenu compte de la grave maladie dont souffrait l'épouse. Le Département de l'économie a rendu une ordonnance le 15 mai 2009 rejetant la requête de mesures provisionnelles. Cette décision a été confirmée par le Tribunal administratif du canton de Neuchâtel (ci-après: le Tribunal administratif) et le Tribunal fédéral (arrêt 2C_483/2009 du 18 septembre 2009).
Par décision du 8 mars 2010, le Département de l'économie a rejeté le recours des intéressés. Il a retenu que A.X._ avait été condamné à un total d'un peu plus de quinze mois d'emprisonnement. Cette peine, bien qu'inférieure aux deux ans fixés par la jurisprudence en relation avec l'art. 8 CEDH, était le résultat d'une multitude d'infractions perpétrées dans différents cantons sur une durée de sept ans. En récidivant régulièrement, l'intéressé avait démontré ne faire aucun cas ni des avertissements de l'autorité ni du respect de la sécurité et de l'ordre publics suisses. Le Département de l'économie a également indiqué que l'épouse était parfaitement au courant de la situation de son époux et qu'elle devait être consciente du risque important qu'une autorisation de séjour lui soit refusée. Elle était déjà malade au moment où elle l'avait épousé et avait pu vivre, entre ses deux mariages, sans la présence d'un époux. Sa maladie s'était peut-être aggravée, mais cet élément n'était pas suffisant pour faire pencher la balance du côté des intérêts privés des intéressés au vu de tous les éléments du dossier.
C. Par arrêt du 26 octobre 2010, le Tribunal administratif a rejeté le recours de A.X._ et B.X._. Il a retenu que le comportement de l'intéressé démontrait que celui-ci se moquait du respect de la sécurité et de l'ordre publics en Suisse. L'intérêt au maintien de cet ordre et à la prévention des infractions pénales prévalait sur l'intérêt privé de A.X._ à demeurer auprès de son épouse.
D. A.X._ et B.X._ ont déposé un recours en matière de droit public et un recours constitutionnel subsidiaire auprès du Tribunal fédéral. Ils lui demandent, sous suite de frais et dépens, principalement, d'annuler l'arrêt du 26 octobre 2010 du Tribunal administratif et d'octroyer une autorisation de séjour à A.X._, subsidiairement, d'annuler ledit arrêt.
Le Service des migrations, le Département de l'économie, le Tribunal administratif et l'Office fédéral des migrations ont conclu au rejet du recours.
Les 22 février et 11 avril 2011, le Département de l'économie a fait parvenir des pièces au Tribunal fédéral.

Considérant en droit:
1. Le Tribunal fédéral examine d'office sa compétence (<ref-law>). Il contrôle librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 43; <ref-ruling> consid. 1 p. 96).
1.1 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 (art. 83 let. c ch. 2 LTF).
D'après l'art. 43 al. 1 de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20), le conjoint étranger du titulaire d'une autorisation d'établissement 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. Tel est le cas en l'espèce, le recourant étant marié depuis le 25 août 2008 avec une personne titulaire d'un permis d'établissement et faisant ménage commun avec elle. Par conséquent, le recours en matière de droit public est recevable sous cet angle.
En outre, entretenant une relation étroite et effective avec son épouse, laquelle a le droit de résider durablement en Suisse (sur cette notion, cf. <ref-ruling> consid. 1.3.1 p. 145 s.; <ref-ruling> consid. 3.1 p. 28), le recourant a également un droit potentiel à une autorisation de séjour découlant de l'art. 8 CEDH. Il en va de même pour l'épouse, de sorte que le recours en matière de droit public est également recevable de ce point de vue.
Déterminer si le droit du recourant s'éteint en application de l'art. 51 al. 2 let. b LEtr, car un des motifs de révocation au sens de l'art. 62 LEtr est réalisé, est une question qui relève du fond et non de la recevabilité (arrêt 2C_36/2009 du 20 octobre 2009 consid. 1.2).
1.2 Au surplus, le recours est dirigé contre une arrêt final (<ref-law>) rendu en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF); en outre, il a été déposé en temps utile (<ref-law>) par les destinataires de l'arrêt attaqué qui ont un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), de sorte qu'il convient d'entrer en matière.
1.3 La voie du recours en matière de droit public étant ouverte, le recours constitutionnel subsidiaire est irrecevable (<ref-law> a contrario).
1.4 Les 22 février et 11 avril 2011, le Département de l'économie a fait parvenir au Tribunal fédéral des pièces datées du 15 février 2011 respectivement du 1er avril 2011, lesquelles sont donc postérieures à l'arrêt attaqué (cf. <ref-law> et <ref-ruling> consid. 4.4.3 p. 128). Ces documents ont, en outre, été produits hors délai et sans qu'un deuxième échange d'écritures n'ait été ordonné. Ils ne peuvent, dès lors, être pris en considération.
2. Les recourants critiquent en vain, dans leur écriture, la constatation des faits et leur appréciation par le Tribunal administratif. Formulés sur un mode purement appellatoire, ces éléments ne peuvent être pris en compte par le Tribunal fédéral (<ref-law>; <ref-ruling> consid. 3 p. 104), de sorte que le présent arrêt sera fondé sur les faits retenus par le Tribunal administratif.
3. En vertu de l'art. 51 al. 2 let. b LEtr, les droits prévus, notamment, à l'art. 43 LEtr (cf. consid. 1.1) s'éteignent s'il existe des motifs de révocation au sens de l'art. 62 LEtr.
3.1 Selon l'art. 62 let. b LEtr, la révocation de l'autorisation de séjour est notamment possible si l'étranger a été condamné à une peine privative de liberté de longue durée ou a fait l'objet d'une mesure pénale prévue aux art. 64 ou 61 CP. Selon la jurisprudence, une peine privative de liberté est de longue durée lorsqu'elle dépasse un an d'emprisonnement (<ref-ruling> consid. 4.2 p. 379) qu'elle soit ou non assortie du sursis (arrêt 2C_758/2010 du 22 décembre 2010). En outre, la peine privative de liberté de longue durée au sens de cette disposition ne peut résulter de l'addition de peines plus courtes (ATF 2C_415/2010 du 15 avril 2011).
En l'espèce, il ressort de l'arrêt entrepris que le recourant a fait l'objet de diverses peines privatives de liberté. La plus longue est une peine d'un an et elle ne dépasse donc pas la limite de douze mois posée par la jurisprudence. En outre, les différentes condamnations du recourant ne peuvent pas être cumulées. Dès lors, le motif de révocation de l'art. 62 let. b LEtr n'est pas réalisé.
En l'espèce, il ressort de l'arrêt entrepris que le recourant a fait l'objet de diverses peines privatives de liberté. La plus longue est une peine d'un an et elle ne dépasse donc pas la limite de douze mois posée par la jurisprudence. En outre, les différentes condamnations du recourant ne peuvent pas être cumulées. Dès lors, le motif de révocation de l'art. 62 let. b LEtr n'est pas réalisé.
3.2 3.2.1 L'art. 62 let. c LEtr prévoit:
"L'autorité compétente peut révoquer une autorisation, à l'exception de l'autorisation d'établissement, ou une autre décision fondée sur la présente loi, dans les cas suivants:
"L'autorité compétente peut révoquer une autorisation, à l'exception de l'autorisation d'établissement, ou une autre décision fondée sur la présente loi, dans les cas suivants:
... c. si l'étranger attente de manière grave ou répétée à la sécurité et l'ordre publics en Suisse ou à l'étranger, les met en danger ou représente une menace pour la sécurité intérieure ou extérieure de la Suisse;
..."
L'art. 80 al. 1 let. a de l'ordonnance fédérale du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201) précise qu'il y a notamment atteinte à la sécurité et à l'ordre publics en cas de violation de prescriptions légales ou de décisions d'autorité. La sécurité et l'ordre publics sont menacés lorsque des éléments concrets indiquent que le séjour en Suisse de la personne concernée conduit selon toute vraisemblance à une atteinte à la sécurité et à l'ordre publics (art. 80 al. 2 OASA).
Il est à noter ici que les conditions de révocation d'une autorisation pour atteinte à la sécurité et à l'ordre publics par le conjoint d'un détenteur d'une autorisation d'établissement sont moins strictes que celles prévues pour le conjoint d'un ressortissant suisse. Dans ce dernier cas, l'atteinte doit être "très grave" (art. 63 al. 1 let. b LEtr; ZBl 112/2011 p. 96, 2C_273/2010). Le Message du 8 mars 2002 concernant la loi sur les étrangers, après avoir défini le terme générique de "sécurité et ordre publics", précise qu'ils sont enfreints notamment en cas de violation importante ou répétée de prescriptions légales ou de décisions d'autorité. Tel est aussi le cas lorsque les actes individuels ne justifient pas en eux-mêmes une révocation mais que leur répétition montre que la personne concernée n'est pas prête à se conformer à l'ordre en vigueur (FF 2002 3564 ad art. 61; cf. aussi Marc Spescha, in: Spescha/Thür/Zünd/Bolzli [éd.], Migrationsrecht, 2e éd., 2009, no 7 ad art. 62 LEtr p. 148).
D'une façon générale, la pratique développée sous l'empire de l'ancienne loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113), en vigueur jusqu'au 31 décembre 2007, reste valable pour l'application des différents motifs de révocation (arrêt 2C_793/2008 du 27 mars 2009 consid. 2.1 et les références citées). L'art. 9 al. 2 let. b LSEE prévoyait la révocation de l'autorisation de séjour, notamment, lorsque l'étranger donnait lieu à des plaintes graves. Correspond plus au nouveau droit, l'art. 10 al. 1 let. b LSEE qui permettait d'expulser l'étranger de Suisse "si sa conduite, dans son ensemble, et ses actes permettent de conclure qu'il ne veut pas s'adapter à l'ordre établi dans le pays qui lui offre l'hospitalité ou qu'il n'en est pas capable". Selon l'art. 16 al. 2 du règlement d'exécution de la loi sur le séjour et l'établissement des étrangers du 1er mars 1949 (RSEE; RO 1949 p. 243), en vigueur jusqu'au 31 décembre 2007, l'expulsion pouvait paraître fondée notamment "si l'étranger contrevient gravement ou à réitérées fois à des dispositions légales ou à des décisions de l'autorité". Ces dispositions ont ainsi une teneur similaire aux art. 62 let. c LEtr et 80 al. 1 let. a OASA cités ci-dessus. Dès lors, en principe, la jurisprudence établie au regard de l'art. 10 al. 1 let. b LSEE peut être appliquée dans le cadre du nouveau droit et permet de mieux cerner la notion d'atteinte grave ou répétée à la sécurité et l'ordre publics en Suisse (cf. à cet égard Andreas Zünd/Ladina Arquint Hill, Beendigung der Anwesenheit, Entfernung und Fern-haltung, in: Uebersax/Rudin/Hugi Yar/Geiser [éd.], Ausländerrecht, 2e éd., 2009, no 8.29 p. 326, ainsi que Silvia Hunziker, in: Caroni/ Gächter/Turnherr [éd.], Bundesgesetz über die Ausländerinnen und Ausländer (AuG), 2010, no 30 ss ad art. 62 LEtr).
3.2.2 Le recourant a commencé son activité délictueuse à peine arrivé en Suisse. Il est, en effet, entré dans notre pays le 2 avril 2002 et sa première condamnation date du 10 juin 2002. Il a fait l'objet de six condamnations pour, notamment, un grand nombre de vols. Certes, ces condamnations ne sanctionnent pas des actes d'une gravité extrême, en revanche, les délits commis par le recourant s'étendent sur de nombreuses années. Il n'a, en outre, pas respecté le délai de départ pour quitter la Suisse qui avait été fixé au 21 mai 2003, à la suite du rejet de sa demande d'asile initiale. La multiplication des infractions commises par le recourant démontre qu'il a attenté de manière répétée à la sécurité et à l'ordre publics en Suisse. L'intéressé n'a tenu aucun compte des avertissements qui lui ont été adressés (condamnations à des peines d'emprisonnement avec sursis). Malgré sa condamnation à douze mois d'emprisonnement pour vols, il a continué à en perpétrer à plusieurs reprises. Rien - pas même la détention - n'a réussi à le détourner de ses activités délictueuses, comme l'atteste, par exemple, le rapport de police du 10 juin 2009 dont il ressort qu'il reconnaît le vol qui lui est reproché.
Il découle de l'ensemble de ces éléments que le recourant réalise le motif de révocation d'autorisation de l'art. 62 let. c LEtr.
Il découle de l'ensemble de ces éléments que le recourant réalise le motif de révocation d'autorisation de l'art. 62 let. c LEtr.
3.3 3.3.1 De même que sous l'ancien droit, lorsqu'il existe une cause de refus d'autorisation de séjour, celui-ci ne se justifie que si la pesée des intérêts à effectuer dans le cas d'espèce ne fait pas apparaître la mesure comme disproportionnée. Il convient donc de prendre en considération, dans la pesée des intérêts publics et privés en présence, la gravité de la faute commise, le degré d'intégration respectivement la durée du séjour effectué en Suisse et le préjudice que l'intéressé et sa famille auraient à subir en raison de la mesure (cf. art. 96 al. 1 LEtr; <ref-ruling> consid. 4.3 p. 381; arrêts 2C_14/2010 du 15 juin 2010 consid. 6.1; 2C_651/2009 du 1 mars 2010 consid. 4).
Une ingérence dans l'exercice du droit au respect de la vie privée et familiale est également possible selon l'art. 8 § 2 CEDH, à certaines conditions précises (<ref-ruling> consid. 4.3 p. 381). Le maintien de l'ordre public, la prévention des infractions pénales et la mise en oeuvre d'une politique restrictive en matière de séjour des étrangers constituent des buts légitimes au regard de cette disposition conventionnelle (<ref-ruling> consid. 2.2.1 p. 156). Il s'agit également de tenir compte, lors de la pesée des intérêts, de la situation du membre de la famille pouvant rester en Suisse dont le départ à l'étranger ne peut d'emblée être exigé sans autre (<ref-ruling> consid. 2.1 p. 154; <ref-ruling> consid. 4.1 p. 23).
3.3.2 Si le recourant est en Suisse depuis 2002, il aurait dû quitter ce pays en 2003 à la suite du rejet de sa demande d'asile. Or, les années passées dans l'illégalité ne sont pas déterminantes dans la pesée des intérêts (cf. <ref-ruling> consid. 4.6 p. 503, 130 II 39 consid. 4 p. 43). L'intéressé ne s'est, en outre, pas intégré socialement ni professionnellement dans notre pays. Il a, de plus, passé l'essentiel de sa vie en Algérie, puisqu'il n'est arrivé en Suisse qu'à 36 ans. Il a, dès lors, dans son pays des attaches culturelles, sociales et certainement familiales.
Le seul lien que le recourant peut invoquer avec la Suisse est son épouse. A cet égard, le recourant reproche au Tribunal administratif de n'avoir pas correctement pris en compte, dans la pesée des intérêts, l'état de santé de celle-ci qui souffre du sida (stade 3) et bénéficie d'une quadrithérapie. Il est vrai que, ajouté au fait qu'elle est de confession chrétienne, un départ de l'épouse pour l'Algérie n'est pas envisageable. Toutefois, cet aspect ne saurait avoir un poids déterminant. Selon les juges cantonaux en effet, la recourante pourra trouver un appui auprès des paroissiens de l'église qu'elle fréquente. Dès lors, s'il convient de ne pas nier le soutien important que le recourant apporte à son épouse, il pourra en partie y être ainsi pallié, sans oublier, le cas échéant, les différents types d'aide proposés par les services sociaux. En outre, il ressort de l'arrêt attaqué que l'intéressée connaissait le comportement délictueux de son conjoint et, contrairement à ce qu'elle affirme, elle devait se douter, au moment de se marier, que ce comportement serait susceptible de conduire à un refus d'autorisation de séjour.
Compte tenu de l'ensemble des circonstances, en particulier de la répétition des infractions commises par le recourant qui persiste dans la délinquance, il apparaît que l'intérêt public à l'éloigner de Suisse l'emporte sur l'intérêt privé de ce dernier et de son épouse à pouvoir vivre dans notre pays. En rendant l'arrêt attaqué, le Tribunal administratif n'a donc pas violé le droit fédéral; en particulier, il a appliqué correctement les art. 51 al. 2 let. b et 62 let. c LEtr, ainsi que 8 CEDH.
4. Le recourant invoque la jurisprudence Reneja (<ref-ruling>) - qui demeure valable sous la LEtr (<ref-ruling> consid. 4.3 et 4.4 p. 381 ss) - applicable au conjoint étranger d'un ressortissant suisse. Selon celle-ci, une condamnation à deux ans de privation de liberté constitue la limite à partir de laquelle, en général, il y a lieu de refuser l'autorisation de séjour, quand il s'agit d'une première demande d'autorisation ou d'une requête de prolongation d'autorisation déposée après un séjour de courte durée. Or, le recourant avance qu'il n'a, en définitive, été condamné qu'à quinze mois et dix jours d'emprisonnement, ainsi qu'à 920 heures de travail d'intérêt général.
Cette limite de deux ans ne constitue pas une limite absolue et a été fixée à titre indicatif (ATF <ref-ruling> consid. 4.3 p. 24; <ref-ruling> consid. 4.1 p. 185 et les références citées). Elle doit ainsi être appréciée au regard de toutes les circonstances du cas d'espèce. Or, dans le présent cas, l'accumulation d'infractions permet de s'éloigner de la limite des deux ans de détention. De plus, cette pratique est applicable en cas de demande du conjoint d'un ressortissant suisse alors que l'épouse du recourant est titulaire d'une autorisation d'établissement.
5. Compte tenu de ce qui précède, le recours en matière de droit public doit être rejeté dans la mesure de sa recevabilité.
Succombant, les recourant doivent supporter les frais judiciaires (cf. <ref-law>) solidairement entre eux. Il n'est pas alloué de dépens (cf. <ref-law> a contrario).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière de droit public est rejeté dans la mesure où il est recevable.
2. Le recours constitutionnel subsidiaire est irrecevable.
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é au mandataire des recourants, au Service des migrations, au Département de l'économie et à la Cour de droit public du Tribunal administratif du canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 4 mai 2011
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Zünd Kurtoglu-Jolidon