Faits:
A. A.X._, ressortissant algérien, est arrivé en Suisse le 2 avril 2002. Il a déposé une demande d'asile, qui a été rejetée par décision de l'Office fédéral des réfugiés du 13 août 2002, confirmée le 25 mars 2003 par la Commission de recours en matière d'asile. Un délai de départ échéant le 21 mai 2003 lui a été imparti.
A.X._ a été condamné à plusieurs reprises pour diverses infractions pénales dont, notamment, les 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 Ministère public du canton de Neuchâtel du 10 juin 2002), cinq jours d'arrêt avec sursis pendant un an pour vol d'importance mineure (ordonnance pénale du Ministère public du canton de Neuchâtel du 21 juin 2002), douze mois d'emprisonnement pour vols, recel et défaut d'avis en cas de trouvaille (jugement du Tribunal d'arrondissement de Zurich du 24 janvier 2006), trois mois d'emprisonnement pour infraction à la 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) et expulsion du territoire suisse pour une durée de trois ans du fait de désobéissance à la police (jugement du Tribunal de police du district de La Chaux-de-Fonds du 26 septembre 2006).
Le 25 août 2008, A.X._ a épousé, à C._, B._, ressortissante congolaise titulaire d'une autorisation d'établissement en Suisse. Il a par la suite demandé l'octroi d'une autorisation de séjour par regroupement familial.
Par décision du 11 février 2009, le Service des migrations du canton de Neuchâtel a rejeté la demande au motif que A.X._ avait porté atteinte à l'ordre public suisse à de nombreuses reprises; il a en outre enjoint celui-ci de quitter sans délai le territoire neuchâtelois.
A.X._ a fait l'objet d'un nouveau rapport de police du 13 mars 2009 pour vol à l'étalage, vol par effraction, voire recel.
Le 13 mars 2009, les époux A.X._ et B.X._ ont recouru au Département de l'économie du canton de Neuchâtel à l'encontre de la décision du 11 février 2009. Ils ont conclu à l'octroi d'une autorisation de séjour; à titre préalable, ils ont demandé que le recours soit doté de l'effet suspensif, de manière à ce que le premier cité puisse rester en Suisse pendant la durée de la procédure.
B. Par ordonnance du 15 mai 2009, le Département de l'économie a rejeté la demande d'effet suspensif.
A.X._ et B.X._ ont déféré ce prononcé au Tribunal administratif du canton de Neuchâtel, qui a rejeté le recours par arrêt du 10 juillet 2009. Cette autorité a considéré qu'en vertu de la législation fédérale sur les étrangers, celui qui dépose une demande d'autorisation de séjour doit en principe attendre la décision à l'étranger. Il peut être autorisé à demeurer en Suisse durant la procédure si les conditions d'admission sont manifestement remplies, ce qui suppose notamment l'absence de tout motif de révocation. Le fait que l'intéressé a attenté de manière grave ou répétée à la sécurité et à l'ordre public en Suisse ou à l'étranger constitue un motif de révocation. En l'occurrence, un tel motif serait réalisé, le recourant ayant, au vu de la liste des infractions retenues contre lui, porté des atteintes répétées à l'ordre public suisse. Les juges cantonaux ont également relevé que, depuis le rejet définitif de sa demande d'asile au printemps 2003, le recourant séjournait illégalement sur le territoire suisse. Par conséquent, c'était à bon droit que le Service des migrations avait rejeté la requête d'effet suspensif.
C. Agissant par la voie du recours en matière de droit public et du recours constitutionnel subsidiaire, A.X._ et B.X._ demandent au Tribunal fédéral, principalement, de réformer l'arrêt attaqué en ce sens que le recours interjeté le 13 mars 2009 est doté de l'effet suspensif et, subsidiairement, d'annuler la décision entreprise, le tout sous suite de frais et dépens. A titre préalable, ils requièrent que leur recours au Tribunal de céans ait effet suspensif et qu'aucune mesure d'exécution ne soit mise en oeuvre jusqu'à ce qu'il soit statué sur son mérite.
L'autorité précédente, le Département de l'économie, le Service des migrations, ainsi que l'Office fédéral des migrations proposent de rejeter le recours.
Par ordonnance présidentielle du 6 août 2009, il a été décidé qu'aucune mesure d'exécution de la décision attaquée ne pourrait être prise jusqu'au prononcé sur la requête d'effet suspensif.

Considérant en droit:
1. La demande de regroupement familial qui est à la base de la présente affaire est postérieure au 1er janvier 2008, date de l'entrée en vigueur de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20). Elle est donc régie par cette nouvelle loi (art. 126 al. 1 LEtr).
2. 2.1 Les décisions rendues dans des causes de droit public peuvent en principe être attaquées par la voie du recours en matière de droit public (<ref-law>). Toutefois, un tel recours est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit (art. 83 lettre c ch. 2 LTF). En l'espèce, l'arrêt attaqué confirme un prononcé rendu dans le cadre d'une procédure d'autorisation de séjour au titre du regroupement familial, par lequel le Département de l'économie, en refusant la requête d'effet suspensif, a décidé que le recourant devait attendre l'issue de ladite procédure à l'étranger. Dès lors que les recourants sont mariés, que l'épouse est titulaire d'une autorisation d'établissement en Suisse et qu'il n'est pas contesté qu'ils font ménage commun, l'époux peut à première vue se prévaloir d'un droit à une autorisation de séjour en vertu de l'art. 43 LEtr. Il s'ensuit que l'exception prévue à l'art. 83 lettre c ch. 2 LTF n'est pas réalisée, étant précisé que, sous l'angle de la recevabilité, il n'y a pas lieu de se demander si ce droit est véritablement fondé. Le recours en matière de droit public est donc ouvert (cf. arrêt 2D_98/2008 du 12 décembre 2008 consid. 1.2).
2.2 L'arrêt attaqué ne se prononce pas sur le bien-fondé de l'autorisation de séjour sollicitée par le recourant, mais uniquement sur l'obligation qui lui est imposée de se rendre à l'étranger et d'y rester jusqu'à l'issue de la procédure. La décision entreprise est donc une décision incidente rendue dans le cadre d'une procédure d'autorisation de séjour. Elle ne peut dès lors faire l'objet d'un recours que si elle satisfait aux exigences de l'<ref-law>. Selon cette disposition, les décisions incidentes notifiées séparément qui ne concernent ni la compétence ni les demandes de récusation peuvent faire l'objet d'un recours notamment si elles peuvent causer un préjudice irréparable (lettre a), lequel doit être de nature juridique (<ref-ruling> consid. 1.3.4 p. 36 et la jurisprudence citée). Il faut admettre que la confirmation de l'obligation pour le recourant de quitter la Suisse et d'attendre à l'étranger le résultat de la procédure de regroupement familial qu'il a entamée peut lui causer un préjudice irréparable de nature juridique (cf. arrêt 2C_378/2007 du 14 janvier 2008 consid. 2.3.2, in RtiD 2008 II p. 179; arrêt 2D_98/2008 précité consid. 1.3). Celui-ci découle du fait qu'il se trouverait empêché de rester en Suisse avec son épouse qui, en vertu de son autorisation d'établissement, est en droit d'y résider, alors que, comme on l'a vu, il peut a priori se prévaloir de l'art. 43 LEtr. La décision incidente attaquée est donc sujette à recours au Tribunal fédéral.
2.3 Au surplus, interjeté par des parties directement touchées par la décision attaquée et qui ont un intérêt digne de protection à son annulation ou sa modification (cf. <ref-law>), le recours en matière de droit public est dirigé contre un jugement rendu par un tribunal supérieur statuant en dernière instance cantonale (cf. art. 86 al. 1 lettre d et al. 2 LTF). Déposé dans le délai (cf. <ref-law>) et la forme (cf. <ref-law>) prévus par la loi, il est en principe recevable.
Il s'ensuit que le recours constitutionnel subsidiaire interjeté dans la même écriture (cf. <ref-law>) est irrecevable (cf. <ref-law>).
2.4 Le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si ces faits ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>).
2.5 La décision dont est recours portant sur des mesures provisionnelles, seule peut être invoquée la violation des droits constitutionnels (cf. <ref-law>; Thomas Merkli, Vorsorgliche Massnahmen und die aufschiebende Wirkung bei Beschwerden in öffentlich-rechtlichen Angelegenheiten und subsidiären Verfassungsbeschwerden, ZBl 109/2008 p. 431).
3. 3.1 Selon l'art. 17 LEtr, l'étranger entré légalement en Suisse pour un séjour temporaire qui dépose ultérieurement une demande d'autorisation de séjour durable doit attendre la décision à l'étranger (al. 1). Il peut être autorisé à séjourner en Suisse durant la procédure si les conditions d'admission sont manifestement remplies (al. 2). Il faut en déduire que le requérant ne peut prétendre à séjourner en Suisse durant la procédure que s'il est évident qu'il possède un droit à obtenir une autorisation de séjour durable (arrêts 2D_98/2008 précité consid. 4.3, 2C_35/2009 du 13 février 2009 consid. 6.5). Ces règles s'appliquent a fortiori aux étrangers qui séjournent illégalement en Suisse (Message du 8 mars 2002 concernant la loi sur les étrangers, FF 2002 3534 ch. 2.3; Peter Uebersax, in Ausländerrecht, 2e éd., 2009, no 7.332).
Aux termes de l'art. 6 al. 1 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), les conditions d'admission visées à l'art. 17 al. 2 LEtr sont manifestement remplies notamment lorsque les documents fournis attestent d'un droit découlant de la législation interne ou du droit international public à l'octroi d'une autorisation de séjour, lorsqu'aucun motif de révocation au sens de l'art. 62 LEtr n'existe et que la personne concernée accepte de collaborer au sens de l'art. 90 LEtr.
D'après l'art. 43 al. 1 LEtr, le conjoint étranger du titulaire d'une autorisation d'établissement a droit à l'octroi d'une autorisation de séjour, à condition de vivre en ménage commun avec lui. Toutefois, selon l'art. 51 al. 2 LEtr, le droit en question s'éteint notamment s'il existe des motifs de révocation au sens de l'art. 62 LEtr. Selon cette dernière disposition, 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 notamment 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 (lettre c). D'après l'art. 80 al. 1 OASA, il y a atteinte à la sécurité et à l'ordre publics notamment en cas de violation de prescriptions légales ou de décisions d'autorités (lettre a). 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). S'agissant des différents motifs de révocation, 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 largement valable (arrêt 2C_793/2008 du 27 mars 2009 consid. 2.2).
3.2 Lorsqu'il est amené à se prononcer sur une décision refusant à l'étranger la possibilité d'attendre en Suisse l'issue de la procédure, le Tribunal fédéral vérifie seulement si l'autorité judiciaire cantonale a respecté l'ordre constitutionnel (cf. consid. 2.5 ci-dessus) en considérant, compte tenu des éléments en sa possession au moment de l'arrêt attaqué, que les conditions d'admission de la demande n'étaient pas manifestement remplies au sens de l'art. 17 al. 2 LEtr. Sa décision ne préfigure en rien l'issue de la procédure d'autorisation de séjour (arrêt 2D_98/2008 précité consid. 4.3).
4. 4.1 En se plaignant d'un déni de justice prohibé par l'art. 29 al. 1 Cst., les recourants reprochent à l'autorité précédente de ne pas avoir pris en considération certains éléments de fait. Les juges cantonaux n'auraient en effet pas tenu compte du fait que la recourante, souffrant du SIDA et se trouvant sous quadrithérapie, a besoin d'un soutien constant de son mari, comme l'atteste un certificat médical du 26 mai 2009, produit à l'appui du recours interjeté devant l'autorité précédente. La décision entreprise serait en outre contraire à l'art. 8 CEDH, dans la mesure où elle conduit à renvoyer le recourant en Algérie, alors que son épouse ne pourrait l'y rejoindre du fait de son état de santé et parce qu'elle est de confession chrétienne. Le prononcé attaqué serait aussi arbitraire et disproportionné: au vu du préjudice extrêmement grave que causerait la séparation des époux, la pesée des intérêts pencherait manifestement dans le sens d'autoriser le recourant à demeurer en Suisse pendant la durée de la procédure.
4.2 Au moment de son mariage, le 25 août 2008, le recourant séjournait illégalement en Suisse, et ce depuis l'échéance du délai de départ qui lui avait été imparti après le rejet définitif de sa demande d'asile, soit depuis le 21 mai 2003. Compte tenu également du fait que son mariage avec une titulaire d'une autorisation d'établissement est récent, il n'est à tout le moins pas arbitraire - au sens où cela contredirait clairement la situation de fait, violerait gravement une norme ou un principe juridique clair et indiscuté ou encore heurterait de manière choquante le sentiment de la justice et de l'équité (cf. <ref-ruling> consid. 2.1 p. 211 et les références) - de lui opposer l'art. 17 LEtr.
Il n'est pas davantage insoutenable de considérer qu'au vu du nombre et de la nature des infractions retenues à l'encontre du recourant, celui-ci a attenté de manière répétée à la sécurité et l'ordre publics suisses, de sorte que le motif de révocation de l'art. 62 lettre c LEtr n'est pas a priori exclu. Il n'est par conséquent pas non plus dépourvu de sens d'admettre que les conditions dont les art. 43 al. 1 et 51 al. 2 en relation avec l'art. 62 LEtr font dépendre l'octroi d'une autorisation de séjour ne sont pas manifestement réunies et qu'ainsi le recourant tombe sous le coup de la règle générale de l'art. 17 al. 1 et ne peut bénéficier de l'exception prévue par l'art. 17 al. 2 LEtr. La décision attaquée échappe ainsi au grief d'arbitraire. Quant au grief de violation du principe de la proportionnalité, à supposer qu'il ait une portée propre (cf. à ce sujet <ref-ruling> consid. 4.3 p. 158), les recourants le soulèvent en relation avec la pesée des intérêts qui devrait selon eux présider à la décision litigieuse. Or, l'art. 17 LEtr fait dépendre la décision relative au séjour en Suisse pendant la procédure du seul point de savoir si les conditions d'admission de l'étranger sont manifestement remplies. Par conséquent, le grief en question tombe à faux au regard de cette disposition.
Au surplus, les critiques que les recourants formulent en dénonçant un déni de justice relèvent plutôt de la violation du droit d'être entendu garanti par l'art. 29 al. 2 Cst. Or, si elle comprend notamment le droit pour l'intéressé de produire des preuves pertinentes et d'obtenir qu'il soit donné suite à ses offres de preuves pertinentes, cette garantie constitutionnelle n'empêche pas l'autorité de mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude qu'elles ne pourraient l'amener à modifier son opinion (<ref-ruling> consid. 2.1 p. 429 et les références). En l'occurrence, on ne peut reprocher aux premiers juges d'avoir renoncé à administrer les preuves se rapportant à la maladie de la recourante et au fait qu'elle aurait constamment besoin du soutien de son mari, en considérant que ces circonstances, à supposer qu'elles fussent avérées, n'étaient pas de nature à faire apparaître comme manifestement remplies les conditions d'admission du recourant, qui sont seules déterminantes du point de vue de l'art. 17 al. 2 LEtr. Au vu des infractions retenues à l'encontre du recourant, qui sont - comme il a été dit - susceptibles de constituer un motif de révocation, on ne saurait en effet qualifier d'arbitraire cette appréciation anticipée des preuves. Le grief de violation du droit d'être entendu est donc mal fondé.
S'agissant du grief de violation de l'art. 8 CEDH, le Tribunal de céans a déjà eu l'occasion de relever que cette disposition conventionnelle ne confère pas un droit à attendre en Suisse l'issue de la procédure d'autorisation de séjour (arrêts 2C_11/2007 du 21 juin 2007 consid. 2.3.3, 2P.3/1997 du 27 février 1997 consid. 2b; cf. aussi arrêt 5P.191/2003 du 9 juillet 2003 consid. 4, in FamPra.ch 2003 p. 958). Partant, le recours est mal fondé à cet égard aussi.
5. Vu ce qui précède, le recours en matière de droit public doit être rejeté.
Avec la présente décision, la requête d'effet suspensif devient sans objet.
Succombant, les recourants supportent les frais judiciaires, solidairement entre eux (cf. art. 66 al. 1 et 5 LTF) et n'ont pas droit à des dépens (cf. <ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours constitutionnel subsidiaire est irrecevable.
2. Le recours en matière de droit public est rejeté.
3. Des frais judiciaires de 1'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 18 septembre 2009
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Müller Vianin