Faits:
A. Par jugement du 11 novembre 1994, le Tribunal du district de Grandson a prononcé le divorce des époux A._ et , et attribué à la mère l'autorité parentale sur leur fille B._, née en 1991. Le Tribunal a également ratifié, pour faire partie intégrante du dispositif du jugement, la convention sur les effets accessoires du divorce prévoyant que le père contribuerait aux frais d'entretien et d'éducation de sa fille par le versement d'une pension alimentaire mensuelle de 1'350 fr. jusqu'à dix ans révolus, de 1'500 fr. jusqu'à seize ans révolus et de 1'650 fr. jusqu'à la majorité et au-delà si, la majorité atteinte, sa fille n'avait pas terminé ses études ou sa formation professionnelle.
B. Le 17 novembre 2009, le père a ouvert action devant l'Autorité tutélaire du district de Neuchâtel en suppression de la contribution d'entretien en faveur de sa fille, avec effet rétroactif au 17 novembre 2008. Il a fait valoir que sa situation financière ne lui permettait plus de verser une pension en raison de la modification notable de ses conditions de vie. B._ a conclu au rejet de la demande et précisé qu'elle entrerait à l'Université après l'obtention de sa maturité fédérale, à la prochaine rentrée académique.
Par jugement du 19 mars 2010, l'Autorité tutélaire a rejeté l'action du père en ce qui concerne les contributions d'entretien dues pendant la minorité de sa fille, mais elle a supprimé les contributions d'entretien dès le 2 juin 2009. L'autorité de première instance a retenu que le père réalisait un revenu mensuel net de 9'346 USD et supportait des charges incompressibles de 9'125,97 USD, de sorte qu'il ne disposait pas du montant nécessaire pour couvrir son minimum vital élargi majoré de 20 %.
C. Statuant le 6 octobre 2010 sur le recours interjeté par B._, l'Autorité tutélaire de surveillance du Tribunal cantonal neuchâtelois a partiellement réformé le jugement de première instance en ce sens que les contributions d'entretien mensuelles sont fixées à 500 fr. dès le 2 juin 2009.
D. Par acte du 8 novembre 2010, le père a interjeté un recours en matière civile au Tribunal fédéral contre cet arrêt. Il conclut principalement à sa réforme en ce sens que les contributions d'entretien en faveur de sa fille sont supprimées dès le 2 juin 2009, subsidiairement à son annulation et au renvoi de la cause aux autorités cantonales.
Invitées à se déterminer, l'intimée conclut au rejet du recours et l'autorité cantonale se réfère aux considérants de son arrêt.

Considérant en droit:
1. 1.1 L'arrêt attaqué est une décision en matière civile (<ref-law>). Comme le litige porte sur la modification de la contribution d'entretien en faveur d'un enfant majeur, le recours a pour objet une affaire pécuniaire (<ref-ruling> consid. 2 p. 395), dont la valeur litigieuse atteint 30'000 fr. (art. 51 al. 1 let. a et al. 4, art. 74 al. 1 let. b LTF). Interjeté contre une décision finale (<ref-law>) en temps utile (<ref-law>), par la partie qui a succombé dans ses conclusions prises devant l'autorité précédente (art. 76 al. 1 aLTF, dans la version en vigueur jusqu'au 31 décembre 2010), le recours est recevable au regard de ces dispositions.
1.2 Le recours en matière civile est recevable contre les décisions prises par les autorités cantonales de dernière instance (<ref-law>). Dans le canton de Neuchâtel, la loi concernant l'introduction du code civil suisse du 15 août 2008 (abrogée le 1er janvier 2011, ci-après: aLICC/NE) prévoyait que les contestations en matière d'obligation d'entretien et de dette alimentaire (art. 279, 286, al. 2, 289, al. 2, 291, 292, 294, 328, al. 1, 329, al. 3 CC) devaient être tranchées par l'autorité tutélaire, sans préjudice des compétences du juge du divorce (art. 8 al. 2 aLICC/NE). Cette solution est contraire au droit fédéral en vertu duquel le juge du divorce est compétent ratione materiae en matière de modification litigieuse des contributions d'entretien fixées dans un jugement de divorce (art. 134 al. 3 2e phr. CC). Il s'ensuit que l'autorité tutélaire de surveillance n'était pas compétente pour trancher le présent litige.
Cela ne signifie toutefois pas que l'arrêt attaqué doive être annulé d'office. Selon une jurisprudence constante, lorsque la loi ne consacre pas expressément la nullité d'un acte violant une disposition légale, cette conséquence juridique ne doit être admise que si elle résulte du sens et du but de la disposition en cause (<ref-ruling> consid. 3a/aa p. 98 s.; <ref-ruling> consid. 4a p. 155). En d'autres termes, il n'y a lieu d'admettre la nullité, hormis les cas expressément prévus par la loi, qu'à titre exceptionnel, lorsque les circonstances sont telles que le système d'annulabilité n'offre manifestement pas la protection nécessaire; entrent principalement en considération comme motifs de nullité de graves vices de procédure ainsi que l'incompétence qualifiée de l'autorité qui a rendu la décision (<ref-ruling> consid. 3.3 p. 434; <ref-ruling> consid. 3a/aa p. 99 et les références citées).
En l'espèce, on ne saurait parler d'incompétence qualifiée de l'autorité tutélaire de surveillance, dès lors qu'elle assume la fonction d'autorité de dernière instance cantonale statuant sur recours, en vertu du droit cantonal (art. 394 al. 1 du code de procédure civile neuchâtelois du 30 septembre 1991 abrogé le 1er janvier 2011; aCPC/NE). Dans ces circonstances, l'arrêt cantonal entrepris est seulement annulable. Or, les parties ont procédé sans remettre en cause la compétence ratione materiae des autorités tutélaires. Il n'y a donc pas lieu d'annuler l'arrêt attaqué.
2. Le recours en matière civile peut être formé pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Compte tenu de l'exigence de motivation posée à l'<ref-law>, le Tribunal fédéral n'examine, en principe, que les griefs soulevés; il n'est pas tenu de traiter, à l'instar d'une autorité de première instance, toutes les questions juridiques qui se posent, lorsqu'elles ne sont plus discutées devant lui (<ref-ruling> consid. 1.4 p. 400); il n'entre pas en matière sur les critiques qui ne sont pas motivées conformément à la loi (<ref-ruling> consid. 2.1 p. 245-246).
Le Tribunal fédéral conduit son raisonnement 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>), et si la correction du vice est susceptible d'influencer le sort de la cause (<ref-law>). Le recourant qui soutient que les faits ont été établis de manière manifestement inexacte (<ref-law>), à savoir que les constatations de fait sont arbitraires au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.2.2 p. 252), doit démontrer, par une argumentation précise, en quoi consiste la violation (arrêt 5A_290/2010 du 28 octobre 2010 consid. 2.3).
3. Le recourant fait grief à l'autorité précédente de ne pas avoir retenu, de manière arbitraire, des éléments de fait déterminants (<ref-law>) et, partant, d'avoir violé la maxime inquisitoire (art. 280 al. 2 aCC), dès lors qu'elle a refusé de prendre en considération les frais relatifs à l'amortissement de la dette hypothécaire de son logement, dont il a apporté la preuve par pièces. L'intimée soutient que le recourant a tardé à faire la preuve de ses allégations, de sorte que ces pièces sont irrecevables.
3.1 Le recourant avait allégué, dans sa demande du 17 novembre 2009, le caractère obligatoire de l'amortissement de la dette hypothécaire dans le système bancaire américain et indiqué qu'il entendait fournir des pièces à ce sujet. Par la suite, il a déclaré qu'il n'avait pas été en mesure d'apporter cette pièce plus tôt dans la procédure, dès lors qu'il lui avait été "extrêmement difficile [...] d'obtenir la confirmation qu'il était impossible de faire quelque chose que le système des prêts bancaires américains n'autorise pas" (n° 3.2 p. 6 du recours). L'autorité précédente a cependant considéré que "les parties avaient tout loisir de produire au cours de la procédure de première instance les pièces qu'elles déposent devant l'Autorité de céans et qui n'ont pas trait à des faits nouveaux qui seraient survenus postérieurement au jugement attaqué; ces pièces sont donc irrecevables et doivent être écartées du dossier" (consid. 1 p. 3 de l'arrêt querellé). Le point de savoir si l'autorité cantonale de recours avait l'obligation de tenir compte des pièces déposées par l'intimé en deuxième instance, dès lors qu'elle entendait modifier la décision des premiers juges peut souffrir de demeurer indécis en l'espèce, la correction du vice n'étant de toute manière pas susceptible d'influencer la solution retenue par l'autorité précédente et, partant, le sort de la cause (<ref-law>) au vu de la double motivation de la décision querellée.
3.2 A juste titre, les juges précédents ont certes rappelé que l'amortissement de la dette hypothécaire, qui ne sert pas à l'entretien, mais à la constitution du patrimoine, n'a en principe pas à être pris en considération pour le calcul du minimum vital (consid. 5 p. 5 de l'arrêt attaqué; arrêt 5C.84/2006 du 29 septembre 2006 consid. 2.2.3). L'autorité cantonale a toutefois considéré que les frais de logement du recourant, qui s'élèvent à 3'713,40 USD par mois, amortissement compris, pour une famille de quatre personnes, sont manifestement excessifs par rapport à ses ressources de 9'346 USD. Or, les dépenses consenties au titre des frais de logement ne peuvent être prises en considération que si elles correspondent à la situation familiale du débiteur, à sa situation économique et aux loyers usuels du lieu (<ref-ruling> consid. 3c; arrêt 5A_470/2008 du 19 janvier 2009 consid. 2). En conséquence, il importe peu que l'amortissement eût dû être ou non pris en considération sur la base des pièces produites par le recourant, car l'intégralité du montant que celui-ci déclare consacrer au logement pouvait ne pas être retenue par l'autorité cantonale pour la détermination de son minimum vital.
Le recourant critique également cette appréciation. Il prétend que le coût moyen d'un logement en Californie correspond usuellement aux 40 % du revenu. Il n'a toutefois pas établi que tel serait effectivement le cas, les pièces auxquelles il se réfère indiquant uniquement le loyer de logements comparables. Or, l'autorité précédente a estimé qu'un logement de ce standing était trop élevé par rapport à ses ressources. Le dossier ne contient aucune pièce relative au budget usuel d'une famille américaine, de sorte que le recourant ne démontre pas que les juges précédents auraient établi les faits de manière manifestement inexacte, ni que leur appréciation des preuves serait insoutenable. Il se borne à substituer sa propre appréciation à celle des juges cantonaux. Par conséquent, son argumentation ne satisfait pas à l'exigence de motivation minimale posée aux art. 42 al. 2 et 106 al. 2 LTF; le grief est ainsi irrecevable (cf. supra consid. 2).
4. Le recourant fait valoir ensuite que les autorités cantonales auraient commis plusieurs erreurs dans la détermination de son minimum vital élargi, notamment quant aux postes relatifs à la base mensuelle, aux frais liés à l'exercice d'une profession et aux frais de formation des enfants mineurs. Selon l'appréciation de l'autorité précédente, les charges du recourant s'élèvent à 7'368 USD et son minimum vital élargi majoré de 20 % se monte à 8'841 USD. Le débiteur de la contribution d'entretien soutient que son minimum vital élargi augmenté de 20 % s'élève à 11'179.46 USD.
4.1 S'agissant de l'entretien d'un enfant majeur n'ayant pas encore achevé sa formation, le parent ne peut en principe y être astreint que lorsque cette contribution n'entame pas son minimum vital élargi augmenté de 20 % (<ref-ruling> consid. 3e p. 207; <ref-ruling> consid. 4b/aa p. 99 ss). La capacité contributive doit être appréciée en fonction des charges effectives du débirentier, étant précisé que seuls les montants réellement acquittés - exempts de toute majoration - peuvent être pris en considération (<ref-ruling> consid. 3a p. 22). La majoration de 20 % ne s'applique qu'à la seule base mensuelle et non aux autres postes du minimum vital (arrêts 5A_476/2010 du 7 septembre 2010 consid. 2.2.3; 5C.107/2005 du 13 avril 2006 consid. 4.2.1). Le juge dispose d'un large pouvoir d'appréciation lorsqu'il fixe la contribution d'entretien (<ref-law>). Le Tribunal fédéral n'intervient que si la juridiction cantonale s'est écartée sans raison des règles établies par la jurisprudence et la doctrine ou si elle s'est appuyée sur des faits qui, dans le cas particulier, ne devaient jouer aucun rôle ou si, au contraire, elle n'a pas tenu compte d'éléments qui auraient absolument dus être pris en considération, ou encore si, d'après l'expérience de la vie, le montant arrêté apparaît manifestement inéquitable au regard des circonstances (<ref-ruling> consid. 5.1 p. 183; <ref-ruling> consid. 4.3 p. 576 et les arrêts cités).
4.2 L'arrêt attaqué constate que le recourant a d'abord admis que le coût de la vie était sensiblement moins élevé en Californie que dans le canton de Neuchâtel, avant de déclarer le contraire. Dès lors que la première affirmation paraissait correspondre au rapport d'enquête sur les prix et les salaires effectuée par l'UBS en 2009, l'autorité cantonale a estimé que les premières données étaient pertinentes. En ce qui concerne les frais indispensables à l'exercice d'une profession et d'une formation pour les enfants mineurs du débiteur, l'autorité précédente s'en est tenue aux allégations du recourant, subsidiairement, faute de pièces, aux frais ordinaires (consid. 7 et 8 p. 6 de l'arrêt entrepris; Circulaire de l'Autorité cantonale inférieure de surveillance des offices des poursuites pour dettes et des faillites du canton de Neuchâtel sur le minimum vital mensuel insaisissable). Sur la base des pièces produites par le recourant, les juges précédents ont estimé - au prix de l'essence aux États-Unis d'Amérique - les frais de déplacement à hauteur de 300 USD par mois et par véhicule (consid. 7 de l'arrêt). Les frais retenus pour ce poste sont élevés, sachant que le prix du gallon d'essence (= 3,785 litres) en Californie (<ref-law>) est nettement moins cher qu'en Suisse. Finalement, il apparaît que l'autorité cantonale a appliqué une majoration de 20 % à l'ensemble des postes du minimum vital du recourant et non au seul montant de base. Au vu de ce qui précède, le minimum vital du recourant a été largement estimé en sa faveur. La détermination de la capacité contributive du recourant n'est entachée d'aucun abus du pouvoir d'appréciation.
Par ailleurs, le recourant se borne à affirmer que les autorités ont retenu des montants inférieurs à ceux qu'il allègue; ce faisant, il n'expose pas en quoi l'arrêt entrepris violerait l'appréciation des preuves ou une disposition légale. Sa critique n'est, sur ces questions, pas suffisante au regard de l'exigence minimale de motivation (<ref-law> et supra consid. 2). Ces griefs sont ainsi irrecevables.
5. Finalement, le recourant reproche à l'autorité précédente d'avoir retranscrit une erreur du jugement de première instance, en omettant de reprendre dans son tableau récapitulatif deux postes des charges, pour un montant de 72 USD. Il s'agit en réalité d'une erreur de plume qui n'a plus été prise en considération dans l'arrêt attaqué et qui n'a eu aucune conséquence sur le montant de la contribution d'entretien. Il ressort en effet de l'arrêt entrepris que le montant global retenu pour les dépenses indispensables à l'exercice d'une profession, à savoir un montant de 747 USD (consid. 7 p. 6 de l'arrêt entrepris), comprend les frais d'assurance (66 USD) et d'assistance routière (6 USD; consid. 5 p. 3 du jugement de première instance). Le grief du recourant est donc mal fondé.
6. En définitive, le recours doit être rejeté dans la mesure de sa recevabilité. Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>) et versera à l'intimée, qui s'est déterminée sur le fond, une indemnité à titre de dépens (<ref-law>). Dans ces circonstances, la requête d'assistance judiciaire de l'intimée est sans objet.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La requête d'assistance judiciaire de l'intimée est sans objet.
3. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
4. Une indemnité de 2'000 fr., à verser à l'intimée à titre de dépens, est mise à la charge du recourant.
5. Le présent arrêt est communiqué aux parties et à l'Autorité tutélaire de surveillance du canton de Neuchâtel.
Lausanne, le 30 juin 2011
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Hohl
La Greffière: Carlin