Faits:
A. Le divorce des époux X._ a été prononcé par jugement du Tribunal de première instance du canton de Genève du 29 novembre 2010. L'autorité parentale et la garde sur leurs deux enfants communs, A._, né en 1997, et B._, née en 2001, ont été attribuées à la mère.
Jusqu'au jugement, B._ était inscrite à l'École C._, distante de 500 mètres environ de l'ancien domicile conjugal où vit le père. Une distance de près de quatre kilomètres sépare en revanche cette école du domicile actuel de la mère, l'école la plus proche étant celle de D._ située à 300 mètres seulement.
Dès le 17 janvier 2011, la mère s'est adressée au Service de la protection des mineurs (ci-après: SPMi) pour organiser le changement d'école que requéraient les autorités scolaires. Des contacts ont été pris avec les directions des établissements concernés et la date du changement a été arrêtée au 28 février 2011, date de reprise des cours après les vacances de ski. L'enfant et le père ont été informés de cette décision avant le début des vacances.
B. Le 22 février 2011, X._ a requis une mesure de protection de l'enfant doublée d'une requête de mesures provisionnelles d'extrême urgence en vue du maintien de l'enfant au sein de l'École C._ lors de la rentrée du 28 février 2011. Statuant sur mesures provisionnelles urgentes, avant audition des parties, le Tribunal tutélaire du canton de Genève a fait droit à cette requête par ordonnance du 23 février 2011.
Le 28 mars 2011, après audition des parties et instruction écrite, ledit Tribunal a admis l'opposition de la mère et annulé sa précédente ordonnance.
Statuant sur recours du père, la Cour de justice du canton de Genève l'a rejeté par décision du 6 juin 2011.
C. Le 8 juillet 2011, X._ exerce un recours en matière civile contre cette décision, concluant à son annulation. Il requiert en outre que l'enfant soit entendue, que l'ordonnance du 23 février 2011 soit confirmée, que le maintien de B._ au sein de l'École C._ soit ordonné, qu'il soit fait interdiction à l'intimée d'inscrire l'enfant à l'École D._ ou dans toute autre école ainsi qu'il soit constaté que l'autorité parentale de la mère sera limitée sur ce point. Préalablement, il demande l'octroi de l'effet suspensif et de l'assistance judiciaire gratuite. À l'appui de ses conclusions, il se plaint de la violation des art. 296 et 307 ss CC ainsi que des art. 9 et 29 Cst.
Suite à la détermination de l'intimée, qui a conclu au rejet de la requête d'effet suspensif et a requis l'assistance judiciaire gratuite, la Présidente de la Cour de céans a attribué l'effet suspensif au recours par ordonnance du 19 juillet 2011.
Aucune observation n'a été requise sur le fond.

Considérant en droit:
1. Interjeté en temps utile (<ref-law>), ainsi que dans les formes légales (art. 42 al. 1 et 2 LTF), par une partie qui a été déboutée en dernière instance cantonale (<ref-law> et <ref-law>), contre une décision finale (<ref-law>), prise en application des normes de droit public, en matière de protection de l'enfant (art. 72 al. 2 let. b ch. 7 LTF), le recours en matière civile est recevable au regard de ces dispositions.
2. En substance, la cour cantonale a constaté que la mère était titulaire de l'autorité parentale et de la garde sur les enfants du couple depuis que le divorce était devenu définitif et exécutoire et que, par conséquent, ceux-ci partageaient désormais le domicile de leur mère. En outre, elle a relevé que l'enfant B._ résidait - à teneur du jugement de divorce - principalement auprès de sa mère et qu'aucun élément objectif ne permettait d'établir que le changement d'établissement scolaire irait à l'encontre de ses intérêts. À cet égard, elle précise que le refus exprimé de l'enfant ne suffisait pas, à lui seul, à justifier une mesure de protection, en l'absence de menace concrète de ses intérêts. Elle en a déduit que B._ devait fréquenter l'école la plus proche du domicile de la mère. S'agissant de l'audition de l'enfant requise par le père, la juridiction a estimé qu'elle n'était pas de nature à modifier son appréciation des preuves et a rejeté la requête pour le motif que la mesure requise - qui revient à restreindre l'autorité parentale de la mère - n'intervient que peu de mois après le jugement de divorce rendu après une instruction complète de la situation des époux et ne se justifie pas en l'absence de fait nouveau.
3. Le recourant invoque tour d'abord une violation des art. 296 et 307 ss CC en tant que la cour cantonale a estimé que le cas d'espèce ne s'inscrivait pas dans les exceptions possibles aux prérogatives du parent titulaire du droit de garde. Il fait valoir que le changement d'école n'est absolument pas nécessaire et que l'enfant, âgé de 10 ans, le refuse catégoriquement. En outre, il fait grief à la cour cantonale de ne pas avoir suffisamment tenu compte des circonstances du cas d'espèce, en particulier la fragilité de l'enfant et sa volonté de rester dans l'école de son enfance au sein d'un quartier et d'un environnement qui lui est familier depuis toujours. Il avance encore que la décision de la mère, prise sans le consulter, est clairement abusive et cause à l'enfant un véritable traumatisme. Sur ce point, il conteste que sa fille n'ait éprouvé que de la tristesse comme retenu par la cour cantonale. En outre, la décision de la mère s'inscrirait en totale contradiction avec la situation de garde des enfants, qui vivraient majoritairement auprès de lui. À l'appui de ses allégations, il fait référence à des actes de la procédure de mesures protectrices de l'union conjugale de 2006. Il en déduit que le changement d'école est contraire au bien de l'enfant et que la mesure requise doit être ordonnée. Le recourant se plaint encore d'une violation des art. 9 et 29 Cst. pour le motif que l'enfant n'a pas été entendue, alors qu'il avait requis son audition. Il précise que la cour cantonale a ainsi procédé de manière arbitraire à une appréciation anticipée des preuves et violé son droit d'être entendu en refusant sans motifs l'audition.
4. Saisi d'un recours en matière civile, le Tribunal fédéral applique le droit d'office (<ref-law>) sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut donc admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (<ref-ruling> consid. 2.2). Il ne connaît cependant de la violation des droits fondamentaux que si ce grief a été soulevé et motivé par le recourant (<ref-law> ; <ref-ruling> consid. 3.2; <ref-ruling> consid. 1.4.2). Le recourant doit ainsi indiquer précisément quelle disposition constitutionnelle ou légale a été violée et démontrer, par une argumentation précise, en quoi consiste la violation (<ref-ruling> consid. 1.4; <ref-ruling> consid. 1.4.2). Le Tribunal fédéral n'entre pas en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 3).
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'influer sur le sort de la cause (<ref-law>). Les faits et moyens de preuve nouveaux sont prohibés, à moins de résulter de la décision de l'autorité précédente (<ref-law>).
5. Le recourant invoque tour d'abord une violation des art. 296 et 307 ss CC en tant que la cour cantonale a estimé que le cas d'espèce ne s'inscrivait pas dans les exceptions possibles aux prérogatives du parent titulaire du droit de garde.
5.1 La loi ne définit pas l'autorité parentale. La doctrine l'appréhende comme la responsabilité et le pouvoir légal des parents de prendre les décisions nécessaires pour l'enfant mineur. Il s'agit d'un faisceau de droits et de devoirs des père et mère à l'égard de l'enfant, dont l'étendue varie en fonction de plusieurs facteurs, soit en particulier de l'âge et de la maturité de l'enfant (<ref-ruling> consid. 3.1; VEZ, Commentaire romand, n. 1 ad <ref-law>; MEIER/STETTLER, Droit de la filiation, 2009, n. 442). Quant au droit de garde, il est une composante de l'autorité parentale. Il comprend en particulier la faculté de déterminer le lieu de résidence et le mode d'encadrement de l'enfant (<ref-ruling> consid. 4a; <ref-ruling> consid. 2 et les références citées). En cas de vie séparée des père et mère, le domicile légal de l'enfant se trouve auprès de celui des parents auquel la garde a été attribuée (<ref-law>). Le droit de choisir le lieu de séjour, élément essentiel du droit de garde, comprend la scolarisation de l'enfant au domicile du parent titulaire du droit de garde (<ref-ruling> consid. 3.2).
L'exercice de l'autorité parentale, comme du droit de garde, doit poursuivre en toutes circonstances le bien de l'enfant (<ref-law>). Si le développement de celui-ci est menacé et que les parents n'y remédient pas d'eux-mêmes, ou s'ils sont hors d'état de le faire, l'autorité tutélaire prend les dispositions adéquates pour sa protection. Elle peut, en particulier, donner aux père et mère, d'office ou sur requête, des instructions au sens de l'<ref-law>. Ainsi, elle est habilitée à interdire au parent titulaire du droit de garde d'inscrire l'enfant dans un établissement scolaire donné si un tel changement compromettrait gravement le bien de celui-ci. En règle générale, des difficultés initiales d'intégration ou de langue ne représentent pas un danger sérieux pour l'intérêt de l'enfant. De telles difficultés sont en effet plus ou moins inhérentes à tout changement de domicile, et se présentent, pour l'essentiel, lorsque non seulement le titulaire du droit de garde, mais aussi l'ensemble de la famille, déménage. La perspective d'un changement d'établissement scolaire n'est donc pas de nature, en principe, à mettre le bien de l'enfant sérieusement en danger (<ref-ruling> consid. 3.3).
5.2 Il n'y a pas lieu, en l'espèce, d'examiner si le changement d'école est susceptible de mettre gravement en danger le bien de l'enfant. En effet, l'autorité parentale et la garde sur les enfants du couple X._ ont été attribuées exclusivement à la mère par jugement de divorce du 29 novembre 2010. Or, la scolarisation de l'enfant B._ dans l'école la plus proche de son domicile légal, à savoir au domicile de sa mère (<ref-law>), découle inévitablement de ces attributions. Il s'ensuit que, le prononcé de la mesure requise conduirait à revenir sur une conséquence inéluctable du jugement de divorce. En tant que le recourant se prévaut de la situation antérieure au prononcé du divorce, il ne saurait être entré en matière sur sa demande. La situation familiale des parties ainsi que la répartition des tâches éducatives durant la période de la séparation jusqu'au prononcé judiciaire a été instruite par les juges du divorce lesquels ont précisément décidé d'attribuer l'autorité parentale et la garde à la mère. Aussi, en l'absence d'éléments nouveaux, le recourant ne saurait invoquer la situation antérieure pour empêcher l'exécution du jugement de divorce par la voie de mesures de protection de l'enfant. Mal fondé, le recours doit être rejeté sur ce point.
6. Le recourant se plaint encore d'une violation des art. 9 et 29 Cst. pour le motif que l'enfant n'a pas été entendue, alors qu'il avait requis son audition.
6.1 L'audition des enfants découle directement de l'art. 12 de la Convention du 20 novembre 1989 de l'ONU relative aux droits de l'enfant (CDE, RS 0.107; sur ce point : <ref-ruling>). Cette norme conventionnelle ne consacre toutefois pas de prérogatives plus larges que celles résultant de l'art. 144 al. 2 aCC - depuis le 1er janvier 2011, <ref-law> - (<ref-ruling> consid. 1.1), respectivement de l'<ref-law> (arrêt 5A_46/2007 du 23 avril 2007 consid. 2.1). En vertu de cette dernière disposition, avant d'ordonner une mesure de protection de l'enfant, l'autorité tutélaire ou le tiers nommé à cet effet entend l'enfant personnellement et de manière appropriée, pour autant que son âge ou d'autres motifs importants ne s'opposent pas à l'audition. L'audition de l'enfant constitue à la fois un droit de participation de l'enfant à la procédure qui le concerne et un moyen pour le juge d'établir les faits (arrêt 5C.316/2006 du 5 juillet 2007 consid. 2 non publié aux <ref-ruling>). Le Tribunal fédéral a cependant admis que, lorsque l'enfant a déjà été entendu par un tiers, en général dans le cadre d'une expertise, le juge peut renoncer à l'entendre une nouvelle fois si une audition répétée représente pour l'enfant une charge insupportable (par ex. en cas de conflit de loyauté aigu) et que l'on ne peut attendre aucun nouveau résultat d'une audition supplémentaire ou que l'utilité escomptée est sans rapport raisonnable avec la charge causée par la nouvelle audition. Le juge peut alors se fonder sur les résultats de l'audition effectuée par le tiers pour autant qu'il s'agisse d'un professionnel indépendant et qualifié, que l'enfant ait été interrogé sur les éléments décisifs pour l'affaire à juger et que l'audition, respectivement ses résultats, soient actuels (<ref-ruling> consid. 4).
6.2 En l'espèce, le refus de l'audition de l'enfant ne consacre aucune violation de l'<ref-law> ni des art. 9 et 29 Cst., dès lors que la scolarisation de l'enfant dans l'établissement le plus proche du domicile de la mère constitue une conséquence logique de l'attribution à cette dernière de l'autorité parentale et de la garde sur l'enfant par le jugement de divorce. Il ressort en effet du jugement du 29 novembre 2010 que les enfants ont été entendus à plusieurs reprises durant la procédure et que leur situation a fait l'objet des trois rapports d'enquête du SPMi. L'enfant B._ a ainsi eu l'opportunité de s'exprimer avant qu'il ne soit statué sur son sort. Qui plus est, le changement d'école était clairement envisagé par le SPMi, dont les juges ont suivi les recommandations lors du prononcé du divorce, puisque ce service a invité l'intimée à entreprendre les démarches nécessaires une fois le jugement entré en force. En définitive, en l'absence de tout élément nouveau, la cour cantonale n'a nullement enfreint le droit en jugeant qu'il n'était pas nécessaire, en l'espèce, d'entendre l'enfant.
7. Sur le vu de ce qui précède, le recours doit être rejeté, dans la mesure de sa recevabilité. Les conclusions du recourant étant dépourvues de toutes chances de succès, sa requête d'assistance judiciaire doit être rejetée (<ref-law>) et les frais judiciaires mis à sa charge (<ref-law>). L'intimée n'a pas droit à une indemnité de dépens pour sa détermination sur l'effet suspensif dès lors qu'elle a succombé sur ce point (art. 68 al. 1 et 2 LTF). Quant à la requête d'assistance judiciaire de celle-ci, elle doit être rejetée concernant la détermination sur l'effet suspensif, faute de chances de succès, et déclarée sans objet pour le surplus, le dépôt de réponses sur le fond n'ayant pas été requis.

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 du recourant est rejetée.
3. Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4. La requête d'assistance judiciaire de l'intimée est rejetée s'agissant de la détermination sur l'effet suspensif et déclarée sans objet pour le surplus.
5. Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, autorité de surveillance du Tribunal tutélaire.
Lausanne, le 3 août 2011
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Hohl
Le Greffier: Richard