Faits:
A. A.X._, né en 1969, de nationalité tunisienne, et B.X._, née en 1983, de nationalité macédonienne, se sont mariés en 2002 à Prilly, dans le canton de Vaud, où ils étaient domiciliés. L'épouse étant au bénéfice d'un permis d'établissement, le mari a obtenu une autorisation de séjour.
Le 1er octobre 2003, les époux X._ se sont installés à La Chaux-de-Fonds. Quatre enfants sont nés de cette union, à savoir C._, née en 2003, D._, né en 2005, E._, né en 2006 et F._, née en 2008. Par décision du 12 mai 2005, le Service des migrations du canton de Neuchâtel (ci-après: le Service des migrations) leur a refusé l'octroi d'un permis de séjour et d'établissement dans ce canton, au motif qu'ils étaient précédemment à la charge de l'assistance publique dans le canton de Vaud et qu'ils bénéficiaient également de l'aide sociale depuis leur arrivée dans le canton de Neuchâtel, où leur dette d'assistance s'élevait à 36'000 fr. à la fin de l'année 2004. En outre, ils étaient sans emploi et cette situation était susceptible de perdurer. Enfin, le refus d'une autorisation dans le canton de Neuchâtel ne faisait pas obstacle à leur retour dans le canton de Vaud.
B. Par décision du 19 octobre 2007, le Département de l'économie du canton de Neuchâtel (ci-après: le Département de l'économie) a admis le recours formé par les intéressés, annulé la décision du 12 mai 2005 et renvoyé la cause au Service des migrations pour nouvelle instruction. Il a exposé, en substance, que l'existence d'une convention entre la Suisse et la Macédoine limitait les motifs de refus de changement de canton. Un tel refus n'était, en effet, envisageable que dans la mesure où il existait un motif légal d'expulsion de Suisse et pour autant qu'il respecte le principe de la proportionnalité et paraisse approprié aux circonstances. Selon ledit Département, le fait que les intéressés soient durablement à la charge de l'assistance publique remplissait la première condition. En revanche, la cause devait être renvoyée au Service des migrations afin que celui-ci examine la question de la proportionnalité de la mesure.
C. Le 30 avril 2008, le Service des migrations s'est à nouveau prononcé sur cette cause et il a refusé l'octroi d'une autorisation d'établissement, respectivement de séjour, aux deux époux et à leurs enfants.
Saisi d'un nouveau recours, le Département de l'économie l'a rejeté par décision du 20 janvier 2009, laquelle a été confirmée par arrêt du 27 janvier 2011 du Tribunal administratif (depuis le 1er janvier 2011, la Cour de droit public du Tribunal cantonal) du canton de Neuchâtel (ci-après: le Tribunal cantonal).
D. Agissant par la voie du recours en matière de droit public, A.X._ et B.X._ demandent au Tribunal fédéral, principalement, de réformer l'arrêt du 27 janvier 2011 du Tribunal cantonal en ce sens qu'ils doivent être mis au bénéfice d'une autorisation d'établissement, subsidiairement, d'annuler ledit arrêt et de renvoyer la cause au Tribunal cantonal pour nouvelle instruction et nouvelle décision. Ils ont également demandé l'assistance judiciaire et la désignation de Me Jean Lob en qualité de défenseur d'office. Ils ont enfin requis l'effet suspensif, lequel leur a été octroyé par ordonnance présidentielle du 16 février 2011.
Le Service des migrations a déclaré n'avoir pas d'observations à formuler. Le Tribunal cantonal et le Service juridique du Département de la justice, de la sécurité et des finances concluent au rejet du recours. L'Office fédéral des migrations s'est prononcé hors délai.
Par courrier du 21 juin 2011, le Service des migrations a fait parvenir des pièces au Tribunal fédéral.

Considérant en droit:
1. Le 21 juin 2011, le Service des migrations a fait parvenir au Tribunal fédéral des pièces datées du 16 juin 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. Selon l'art. 83 let. c LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent le déplacement de la résidence dans un autre canton (ch. 6; en vigueur depuis le 1er janvier 2008, RO 2006 5599).
En l'espèce, le droit au permis d'établissement dans le nouveau canton ne constitue qu'une conséquence du droit de changer de domicile d'un canton à l'autre puisque ce droit implique celui à un nouveau permis d'établissement. Le recours doit, ainsi, être traité uniquement sous l'angle du changement de canton. Or, le recours en matière de droit public n'est pas recevable à l'encontre d'une décision concernant ce domaine, et ce même si l'étranger à un droit de changer de canton (arrêts 2C_140/2010 du 17 juin 2010 consid. 2.3 et 2C_886/2008 du 4 mai 2009 consid. 2).
3. 3.1 La voie du recours en matière de droit public n'étant pas ouverte, celle du recours constitutionnel subsidiaire entre en ligne de compte (<ref-law>). La désignation erronée du recours ne porte pas préjudice à son auteur, dans la mesure où celui-ci remplit les exigences légales de la voie de droit qui lui est ouverte (<ref-ruling> consid. 1.2 p. 302/303, 308 consid. 4.1 p. 314).
3.2 La qualité pour former un recours constitutionnel subsidiaire suppose un "intérêt juridique" à l'annulation ou à la modification de la décision attaquée (<ref-law>; cf. <ref-ruling>).
L'ancienne loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RS 1 113) - applicable au présent cas en vertu de l'art. 126 al. 1 LEtr - n'octroie pas de droit à un changement de canton. Par contre, l'art. 1 de la Convention d'établissement et consulaire du 16 février 1888 entre la Suisse et la Serbie (Yougoslavie) (ci-après: la Convention d'établissement; RS 0.142.118.181), initialement conclue avec la Serbie, puis applicable à la Yougoslavie et enfin aux Etats issus de cette dernière, prévoit:
"Les Serbes seront reçus et traités, dans chaque canton de la Confédération, relativement à leurs personnes et à leurs propriétés, sur le même pied et de la même manière que le sont ou pourront l'être à l'avenir les ressortissants des autres cantons. Ils pourront, en conséquence, aller, venir et séjourner temporairement en Suisse, en se conformant aux lois et règlements de police."
La jurisprudence a rappelé que les traités d'établissement encore en vigueur conclus avant la première guerre mondiale sont interprétés, selon un accord tacite et réciproque des Etats contractants, en ce sens qu'ils ne sont applicables qu'aux étrangers au bénéfice d'un permis d'établissement (cf. <ref-ruling> consid. 1a p. 67; cf. aussi <ref-ruling> consid. 2.3).
En conséquence, la recourante, qui possède une autorisation d'établissement de durée indéterminée (art. 6 al. 1 LSEE) valable dans le canton de Vaud, a, en principe, le droit de changer de canton en vertu de l'art. 1 de la Convention d'établissement.
Tel n'est, par contre, pas le cas du recourant, à supposer qu'il puisse se prévaloir de la Convention en cause, car celui-ci détient une autorisation de séjour. Or, la Convention d'établissement n'est applicable qu'aux étrangers au bénéfice d'un permis d'établissement. Dès lors, dépourvu de tout droit de changer de canton, l'époux de la recourante n'a pas d'intérêt juridique à l'annulation ou à la modification de la décision attaquée. Partant, son recours est irrecevable. Cependant, l'autorisation de séjour dont dispose l'intéressé est une autorisation dérivée de l'autorisation d'établissement de son épouse, fondée sur le droit au regroupement familial. Elle suivra donc directement le sort réservé à cette dernière.
3.3 Pour le surplus, interjeté par des parties qui ont succombé dans leurs conclusions, le recours, déposé dans le délai (art. 117 et 100 al. 1 LTF) et la forme (<ref-law>) prévus par la loi, est, de ce point de vue, recevable, puisqu'il est dirigé contre un jugement final (art. 117 et 90 LTF) rendu par un tribunal supérieur statuant en dernière instance cantonale (art. 114 et 86 LTF). Savoir si l'autorisation sollicitée peut être refusée est une question de fond et non de recevabilité (arrêt 2A.594/1996 du 17 mars 1997 consid. 1b).
4. 4.1 Le recours constitutionnel subsidiaire n'est recevable que pour invoquer la violation de droits constitutionnels, grief qui, sous peine d'irrecevabilité, doit faire l'objet d'une motivation spécifique imposée par l'<ref-law> (applicable par renvoi de l'<ref-law>; cf., sur la motivation, <ref-ruling> consid. 4.1 p. 235; <ref-ruling> consid. 2.5 p. 314; <ref-ruling> consid. 1.5 p. 674).
4.2 En l'espèce, c'est en vain que l'on recherche dans le recours une référence au droit constitutionnel, dont aucune norme n'est même mentionnée. Les recourants se contentent, sur un ton purement appellatoire, de critiquer certains aspects de la décision du Tribunal cantonal. Le recours se révèle ainsi irrecevable.
Il en va de même s'agissant de l'invocation du déni de justice. Le Tribunal cantonal a, en effet, clairement exposé, en fonction du droit cantonal, les motifs pour lesquels il s'estimait lié, d'une part, par certains faits, non contestés par les recourants à la suite du premier recours auprès du Département de l'économie, et, d'autre part, par la conclusion juridique retenue s'agissant de l'existence d'un motif d'expulsion. A cet égard, l'<ref-law>, dont le Tribunal fédéral assure le respect d'office, n'est d'aucun secours aux recourants. Ils auraient dû démontrer par une motivation précise, telle qu'exigée par l'<ref-law>, que le Tribunal cantonal avait fait une application arbitraire du droit cantonal en refusant d'entrer en matière sur une décision revêtue de la force de chose jugée. Or, c'est en vain que l'on cherche un début de motivation en ce sens dans le présent recours, l'argument du déni de justice n'étant pas plus motivé que celui de l'arbitraire dans l'application du droit cantonal.
5. Les considérants qui précèdent conduisent à l'irrecevabilité du recours traité comme recours constitutionnel subsidiaire. Succombant, les recourants supporteront solidairement les frais encourus devant le Tribunal fédéral (art. 66 al. 1 et 5 LTF). Il n'est pas alloué de dépens. La cause se révélant dénuée de chances de succès, la requête d'assistance judiciaire est rejetée (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. La requête d'assistance judiciaire est rejetée et il n'est pas alloué de dépens.
3. Les frais judiciaires, arrêtés à 1'500 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 cantonal du canton de Neuchâtel, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 7 juillet 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