Faits:
A. W._, né en 1985, a commencé un apprentissage de carrossier au mois d'août 2001. Il a interrompu cette formation en mars 2003, pour la reprendre dès le 1er octobre 2006. A l'époque, il ne percevait plus de contribution d'entretien de ses parents, les époux X._.
Le 19 juin 2007, le Conseil communal du Locle a adressé à l'Autorité tutélaire du discrict du Locle une requête en paiement de 7'308 francs 90 contre les époux X._. D'après le Conseil communal, ce montant correspondait aux prestations d'aide sociale allouées à W._ depuis le 1er octobre 2006. Le 27 septembre 2007, le Conseil communal du Locle a augmenté ses prétentions en concluant au paiement de 10'562 fr. 25. Par jugement du 30 janvier 2008, l'autorité tutélaire a rejeté la demande.
B. Le Conseil communal du Locle a recouru contre ce jugement devant l'Autorité tutélaire de surveillance du canton de Neuchâtel. Par jugement du 16 mars 2009, cette dernière a admis le recours et condamné les époux X._, solidairement entre eux, à verser 10'562 francs 25 à la Commune du Locle, à raison de 560 francs par mois.
C. Les époux X._ interjettent un recours en matière de droit public contre ce jugement, dont ils demandent l'annulation. L'intimée conclut au rejet du recours.

Considérant en droit:
1. Le Tribunal fédéral examine d'office la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 117, 235 consid. 1 p. 236).
2. 2.1 Aux termes de l'<ref-law>, le Tribunal fédéral connaît des recours contre les décisions rendues dans des causes de droit public (let. a), contre les actes normatifs cantonaux (let. b) ou qui concernent le droit de vote des citoyens ainsi que les élections et votations populaires (let. c). S'agissant de contestations pécuniaires, il n'est pas nécessaire que la valeur litigieuse atteigne un seuil minimal, hormis dans les litiges en matière de responsabilité étatique ou de rapports de travail de droit public (<ref-law> a contrario).
2.2 Le Tribunal fédéral connaît également des recours contre les décisions rendues en matière civile (<ref-law>), mais à la condition, dans les affaires pécuniaires, que la valeur litigieuse atteigne 15'000 francs en matière de droit du travail et de droit du bail à loyer, et 30'000 francs dans les autres cas (<ref-law>). Selon l'<ref-law>, toutefois, le recours en matière civile est recevable indépendamment de la valeur litigieuse si la contestation soulève une question juridique de principe (let. a), si une loi fédérale prescrit une instance cantonale unique (let. b), s'il porte sur une décision prise par une autorité cantonale de surveillance en matière de poursuite pour dettes et faillite (let. c), ou s'il porte sur une décision prise par le juge de la faillite ou du concordat (let. d).
3. Les recourants soutiennent que le jugement entrepris est fondé exclusivement sur du droit public cantonal, de sorte que le recours porte sur une cause en matière de droit public au sens de l'<ref-law>. Les recourants n'invoquent toutefois la violation d'aucune norme de droit public cantonal, mais exclusivement celle de l'<ref-law> et, en relation avec cette disposition, de l'art. 9 Cst. Il convient par conséquent de vérifier si les conditions de recevabilité du recours applicables en l'espèce sont celles du recours en matière de droit civil (<ref-law>) ou du recours en matière de droit public (<ref-law>), étant précisé que l'intitulé erroné d'un recours ne nuit pas à son auteur, pour autant que les conditions de recevabilité du recours qui aurait dû être interjeté soient réunies et qu'il soit possible de convertir le recours dans son ensemble (<ref-ruling> consid. 1.2 p. 382).
4. 4.1 L'<ref-law> met à la charge des père et mère d'un enfant l'obligation de pourvoir à son entretien. Cette obligation dure en principe jusqu'à la majorité de l'enfant (<ref-law>). Toutefois, si à sa majorité, l'enfant n'a pas encore de formation appropriée, les père et mère doivent, dans la mesure où les circonstances permettent de l'exiger d'eux, subvenir à son entretien jusqu'à ce qu'il ait acquis une telle formation, pour autant qu'elle soit achevée dans les délais normaux (<ref-law>). L'enfant peut agir contre son père et sa mère, ou contre les deux ensemble, afin de leur réclamer l'entretien pour l'avenir et pour l'année qui précède l'ouverture de l'action (<ref-law>). Les contributions d'entretien sont dues à l'enfant et sont versées durant sa minorité à son représentant légal ou au parent qui en assume la garde (<ref-law>). La prétention à la contribution d'entretien passe avec tous les droits qui lui sont rattachés à la collectivité publique lorsque celle-ci assume l'entretien de l'enfant (<ref-law>).
4.2 Selon une jurisprudence constante, la contribution d'entretien due à l'enfant par ses père et mère, fondée sur les <ref-law>, relève du droit privé. L'<ref-law> prévoit une cession légale de la créance d'entretien à la collectivité publique (<ref-law>), lorsque celle-ci assume l'entretien de l'enfant (<ref-ruling> consid. 5.2 p. 510; <ref-ruling> consid. 4b p. 163 et les références). La collectivité publique a le droit de réclamer l'entretien en justice, de demander la modification de la contribution alimentaire, de faire aviser les tiers débiteurs et d'exiger des sûretés (<ref-ruling> consid. 2 p. 20 sv. et les références). Elle fait valoir la prétention à la contribution d'entretien de l'enfant, qui est et demeure, malgré la cession, une prétention fondée sur un rapport de droit privé (<ref-ruling> consid. 2a p. 289; arrêt 5A.56/2007 du 6 juin 2007 consid. 1.2, non publié in <ref-ruling>; arrêts 5P.138/2006 du 1er mai 2006 consid. 1.2; 5P.193/2003 du 23 juillet 2003 consid. 1.1.2, in FamPra.ch 2003 p. 971; 5C.193/1998 du 5 juillet 1999 consid. 3a).
4.3 Le jugement entrepris se réfère à l'art. 51 de la loi cantonale neuchâteloise sur l'action sociale, du 25 juin 1996 (RSN 831.0). Aux termes de cette disposition, les personnes tenues de fournir des aliments conformément aux articles 328 et 329 CC, ainsi que les parents tenus à l'obligation d'entretien selon les articles 276 ss CC, doivent participer à la prise en charge de l'aide matérielle accordée au bénéficiaire (al. 1). L'autorité d'aide sociale détermine le montant de la participation d'entente avec le débiteur (al. 2). En cas de désaccord, le litige est porté devant l'autorité tutélaire (al. 3). Le fait que le droit de subrogation prévu par l'<ref-law> pour la collectivité publique qui assume l'entretien de l'enfant est concrétisé dans une disposition du droit public cantonal relatif à l'aide sociale cantonale ne modifie toutefois pas la nature civile de la contestation opposant cette collectivité aux débiteurs de l'entretien; de ce point de vue, le droit cantonal ne revêt pas de portée propre (cf. ANDREAS HAFFTER, Der Unterhalt des Kindes als Aufgabe von Privatrecht und öffentlichem Recht, Thèse, Zurich 1984, p. 218; CYRIL HEGNAUER, Commentaire bernois, 4ème éd. 1997, no 102 ad <ref-law>; KARIN ANDERE, Die familienrechtliche Unterstützungspflicht-Verwandtenunterstützung, in Das schweizerische Sozialhilferecht, 2008, p. 269).
4.4 Le jugement entrepris porte sur l'existence ou non d'une créance subrogatoire de la Commune du Locle contre les époux X._ en raison des prestations d'entretien qu'elle a allouées à leur fils. Il n'a donc pas été rendu dans une cause de droit public au sens de l'<ref-law>, de sorte que le recours en matière de droit public est irrecevable. La valeur litigieuse n'atteint pas, par ailleurs, le seuil prévu par l'<ref-law> et l'on ne se trouve manifestement pas dans l'une des hypothèses visées par l'<ref-law>, de sorte qu'une conversion du moyen de droit choisi par les époux X._ en recours en matière de droit civil, impliquant un transfert de la cause à la IIème Cour de droit civil, n'entre pas en considération.
5. Les recourants voient leur recours déclaré irrecevable, de sorte qu'ils ne peuvent prétendre de dépens à la charge de l'intimée et qu'il supporteront les frais de justice. La demande d'effet suspensif qu'ils ont présentée avec le recours est par ailleurs sans objet compte tenu du présent arrêt.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est irrecevable.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge des recourants.
3. Le présent arrêt est communiqué aux parties et à l'Autorité tutélaire de surveillance du canton de Neuchâtel.
Lucerne, le 23 septembre 2009
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Ursprung Métral