Faits: A. Le 24 juillet 2009, A._ a requis l'Office des poursuites du district de l'Entremont (ci-après: l'office) de notifier à B._, à C._, son ex-employeur avec lequel il était en litige depuis 2008, un commandement de payer la somme de 26'584 fr. plus intérêts à 5 % dès le 1er août 2008. L'office a chargé l'Office des poursuites du district de Martigny de notifier cet acte, portant le n° xxx, à "B._, par Fiduciaire D._, ....". L'acte a été remis à une employée de cette société le 17 août 2009. Il n'a fait l'objet d'aucune opposition. L'office reconnaîtra par la suite que la fiduciaire précitée lui avait clairement indiqué, lors d'un entretien téléphonique portant sur la procédure de la succession répudiée de l'associé gérant de la poursuivie, qu'elle n'était pas habilitée à recevoir notification des actes de poursuite dirigés contre celle-ci et que c'était à la suite d'une erreur qu'il n'avait pas été tenu compte de ce renseignement. Chargé depuis le 20 août 2008 de la défense des intérêts de la poursuivie dans le cadre du conflit de travail précité et autorisé en particulier à la représenter dans tous les actes de poursuite, l'avocat X._ a informé l'office, le 17 novembre 2009, qu'il avait reçu une liste détaillée des poursuites ouvertes contre sa cliente, parmi lesquelles figurait celle dont il a été question ci-dessus. Il l'a invité à lui indiquer si cette dernière était nouvelle ou ancienne, car il n'avait jamais reçu le commandement de payer correspondant, et l'a prié de lui notifier directement cette poursuite. Dans sa réponse du 23 novembre 2009, l'office a renseigné Me X._ sur la notification du commandement de payer du 17 août 2009 en mains de la fiduciaire D._, ainsi que sur l'absence d'opposition, et lui a remis, à toutes fins utiles, une copie dudit commandement de payer. Le lendemain, l'avocat a invité l'office à annuler purement et simplement le commandement de payer en question. Par décision du 1er décembre 2009, l'office a annulé la notification du commandement de payer opérée le 17 août 2009, en précisant qu'à l'entrée en force de sa décision, il procéderait à une nouvelle notification. B. Le 14 décembre 2009, le poursuivant a déposé plainte auprès de l'autorité cantonale inférieure de surveillance en matière de LP, concluant à l'annulation de la décision de l'office du 1er décembre 2009 et à la constatation de la validité de la notification opérée le 17 août 2009. Sa plainte ayant été rejetée par décision du 1er février 2010, il a recouru auprès de l'autorité cantonale supérieure de surveillance. Par jugement du 8 juillet 2011, notifié au poursuivant le 11 du même mois, celle-ci a rejeté le recours, en bref pour les motifs suivants: l'office avait transmis une copie du commandement de payer au mandataire de la poursuivie le 23 novembre 2009; par conséquent, malgré le vice de la notification opérée le 17 août 2009 auprès de la fiduciaire D._, le commandement de payer litigieux était néanmoins parvenu en mains dudit mandataire; ce dernier ayant requis son annulation, l'office était en droit le 1er décembre 2009, le délai de plainte courant du 25 novembre au 4 décembre 2009, de donner suite à cette injonction et d'annuler la notification en question en application de l'art. 17 al. 4 LP. C. Par acte du 22 août 2011, le poursuivant a interjeté un recours en matière civile au Tribunal fédéral, concluant principalement à l'annulation de la décision de l'office, subsidiairement à l'annulation du jugement de l'autorité supérieure de surveillance et au renvoi de la cause à cette autorité pour nouvelle décision dans le sens des considérants. Il fait valoir que le Tribunal cantonal a violé le droit fédéral (art. 17, 64 et 65 LP) en admettant qu'il était loisible à l'office d'annuler une notification antérieure quand bien même une nouvelle notification valable venait d'être effectuée. L'autorité précédente et l'office ont renoncé à se déterminer sur le recours. La poursuivie conclut au rejet de la plainte déposée à l'encontre de la décision de l'office. 