Faits :
A. A.a Le 19 décembre 2003, Compagnie Noga d'importation et d'exportation SA (ci-après: la créancière) a requis un séquestre contre la Fédération de Russie pour une somme de 1'185'600'000 fr. plus intérêts. Ce séquestre a été validé par la poursuite n° 03 116062 A de l'Office des poursuites de Genève.
Sur requête de la créancière du 12 septembre 2005, l'office précité a décidé de procéder à la saisie définitive des tableaux de la collection du Musée national russe Pouchkine de Moscou, qui étaient exposés à la Fondation Pierre Gianadda à Martigny jusqu'au dimanche 13 novembre 2005 et qui devaient en repartir du 15 au 17 novembre 2005, une autre exposition ouvrant ses portes à partir du 18 novembre 2005.
Le 11 novembre 2005, sur délégation de l'office de Genève, l'Office des poursuites de Martigny a donc procédé à la saisie des tableaux en question, au nombre de 54.
A.b Le même jour, la Direction du droit international public du Département fédéral des affaires étrangères a fait savoir à l'office de Genève, avec copie à celui de Martigny, que les biens culturels d'un pays, tels que la collection du Musée Pouchkine, étaient considérés comme des biens affectés à des tâches de puissance publique et que leur insaisissabilité était confirmée par la Convention des Nations Unies sur l'immunité juridictionnelle des Etats et leurs biens, qui avait été adoptée en 2004 et que la Suisse s'apprêtait à ratifier; elle sollicitait donc l'office de ne rien entreprendre qui pût aller à l'encontre du principe de droit international précité.
Par courrier du 15 novembre 2005, adressé au Département des finances, des institutions et de la sécurité du canton du Valais, le préposé de l'office de Martigny a notamment fait valoir les arguments suivants:
En résumé, selon le DFAE, la saisie n'aurait pas eu lieu d'être.
Nous avons soumis cette correspondance à nos conseillers, lesquels nous ont fait savoir que cette argumentation n'était pas de nature à ébranler leur conviction.
-:-
(...)
A ce stade, il nous a ainsi été demandé, sous forme de souhait du gouvernement valaisan, de renoncer à la procédure de saisie (...). Vous comprendrez aisément tout ce que cette démarche peut avoir de délicat pour nous. Toutefois (...), il ne semble pas incompatible avec le respect de la légalité que de souscrire à votre demande.
Il faut pourtant être bien conscient qu'un tel mode de faire ne va pas, selon toute probabilité, entraîner la fin des problèmes auxquels nous sommes confrontés.
Ainsi il n'est guère douteux que le créancier se plaigne par télécopie auprès du juge compétent de la levée de la saisie.
Dans la suite logique, au vu du déplacement annoncé des tableaux à l'étranger, le tribunal va sans doute interdire à titre préprovisionnel urgent tout transfert hors des locaux de la Fondation Gianadda.
Pratiquement les problèmes causés par cette nouvelle situation vont, dès lors, se révéler extrêmement importants. Ainsi, nous avons mis sur pied, non sans difficultés, le transfert - non encore exécuté - des tableaux auprès du Port Franc à Genève dans des locaux sécurisés et climatisés, conformément à ce qui se doit.
Nous avons également traité de toute la problématique des assurances liées au déplacement puis à l'entreposage de ces biens.
Toutes ces mesures - et ce pour autant que l'on puisse encore annuler ces contrats - vont être mises à néant par notre nouvelle décision.
Le prononcé d'effet suspensif que le juge pourrait rendre va nous confronter à une situation très délicate. En effet, nous savons qu'une nouvelle exposition doit intégrer les murs de la Fondation Gianadda cette semaine encore, de sorte qu'il ne sera pas possible d'y laisser les tableaux du musée Pouchkine sous la garde de M. Gianadda.
(...).
Le même jour, 15 novembre 2005 à 12 h 43, le préposé a reçu du Conseil d'Etat du canton du Valais une décision lui recommandant de renoncer à tout acte d'exécution forcée sur les tableaux en cause et l'avisant qu'il serait renoncé à toute action récursoire contre lui au cas où il se conformerait à cette recommandation. Par décision communiquée par télécopie aux parties toujours le même jour, à 13 h 02, et fondée sur l'avis de droit de la Direction du droit international public du DFAE et l'<ref-law>, le préposé a annulé la saisie effectuée le 11 novembre précédent, mis les frais d'exécution par 5'000 fr. à la charge de l'office de Genève et renvoyé à un décompte ultérieur le montant des frais de gérance à charge de la créancière. Il a en outre communiqué sa décision par télécopie à la Fondation et à Léonard Gianadda à 13 h 12, en les informant qu'ils pouvaient disposer des tableaux, mais en les rendant toutefois attentifs au fait qu'il n'était pas certain que ladite décision ne fasse pas l'objet d'une plainte auprès du tribunal compétent, "avec tout ce que cela pourrait impliquer notamment au plan des mesures provisionnelles, éventuellement de blocage".
A.c Les tableaux ont été embarqués le jour même entre 13 h 48 et 14 h 39 sur des camions à destination de la Russie, via l'Allemagne.
A.d Aussitôt qu'elle a eu connaissance de la levée de la saisie, le 15 novembre 2005, la créancière a avisé l'Office des poursuites de Martigny qu'elle allait déposer, dans l'après-midi, une plainte à l'autorité inférieure de surveillance à l'encontre de sa décision; il l'invitait à intervenir auprès de la Fondation Gianadda afin qu'elle ne dispose pas des biens saisis avant décision des autorités de recours. Vers 15 h 30, la créancière a transmis au tribunal la copie d'une plainte. L'original de cette écriture, qui contenait une requête d'effet suspensif urgente au sens de l'<ref-law>, a été déposé à 16 h 15 au greffe du tribunal. Vers 17 heures, l'autorité inférieure de surveillance a accordé l'effet suspensif à la plainte. Sa décision, communiquée par télécopie aux intéressés, faisait interdiction à la Fondation Gianadda de disposer des oeuvres d'art en cause. L'office l'a reçue vers 17 h 41.
A réception de la décision accordant l'effet suspensif, l'Office des poursuites de Martigny a demandé à la police cantonale valaisanne de prendre toutes les mesures pour interdire la sortie des tableaux de la Fondation Gianadda, respectivement pour interdire le départ des camions dans lesquels les tableaux auraient déjà été chargés et, pour le cas où les camions auraient déjà quitté Martigny, pour les arraisonner et ramener les tableaux à la fondation en vue d'y être stockés jusqu'à nouvel ordre. Après avoir appris le départ des camions, l'office a informé la police cantonale qu'il convenait de dérouter vers le port franc le plus proche les camions qu'elle aurait arraisonnés. En outre, en application de l'<ref-law>, il a requis et obtenu des offices des poursuites de Genève et Bâle-Ville l'autorisation de procéder à des mesures sur leur territoire.
Les camions transportant les tableaux ont été interceptés le même jour aux postes de douane de Genève et de Bâle et tous les tableaux litigieux ont été transportés au port franc de Genève, dans un dépôt propriété de l'entreprise initialement mandatée pour les transports et désignée comme gardienne judiciaire des tableaux jusqu'à nouvel ordre.
A.e Le Conseil fédéral ayant décidé, le 16 novembre 2005 vers 18 heures, de lever la saisie avec effet immédiat en application de l'art. 184 al. 3 Cst., l'autorité inférieure de surveillance a considéré, le 25 novembre 2005, que la plainte était devenue sans objet, les tableaux ayant définitivement quitté le territoire helvétique.
B. Le 13 décembre 2005, l'Office des poursuites de Martigny a établi un procès-verbal de non-lieu de saisie, constatant qu'il n'existait plus aucun bien à saisir sur le territoire du district de Martigny et mettant à la charge de la créancière, par prélèvement sur l'avance de 1'000'000 fr. qu'elle avait effectuée, un émolument de 7'430 fr. et des débours par 564'136 fr.
Sur plainte de la créancière, l'autorité inférieure de surveillance a annulé ledit procès-verbal et renvoyé la cause à l'office pour qu'il établisse un nouveau décompte de frais distinguant clairement les frais engendrés par l'exécution de la saisie du 11 novembre 2005 et ceux consécutifs à la décision du 15 novembre 2005 octroyant l'effet suspensif à la plainte du même jour, les premiers devant être supportés par l'office de Martigny et les seconds par la créancière.
Contre cette décision, la créancière a interjeté un recours auprès de l'autorité cantonale supérieure de surveillance en concluant à son annulation dans la mesure où elle mettait à sa charge les frais consécutifs à la décision d'octroi de l'effet suspensif à la plainte, ces frais ne devant pas, à son avis, faire partie des frais de conservation des biens saisis.
Par jugement du 12 juin 2007, l'autorité cantonale supérieure de surveillance a admis partiellement le recours, annulé le procès-verbal litigieux et renvoyé la cause à l'office pour qu'il établisse un nouveau décompte de frais, celui-ci devant distinguer clairement les frais engendrés par les opérations d'exécution de la saisie du 11 au 15 novembre 2005 jusqu'à 13 heures, ceux consécutifs à l'annulation de la saisie dès le 15 novembre 2005 à 13 heures, ceux postérieurs à la décision de l'autorité inférieure de surveillance du 15 novembre 2005 à 17 h 41 octroyant l'effet suspensif à la plainte, ainsi que ceux engendrés par l'annulation définitive de la saisie le 16 novembre 2005 à 18 heures; cela fait, l'office devait mettre à la charge de la créancière les frais engendrés par les opérations d'exécution de la saisie du 11 au 15 novembre 2005 jusqu'à 13 heures et ceux consécutifs à la décision de l'autorité inférieure de surveillance du 15 novembre 2005 à 17 h 41 octroyant l'effet suspensif à la plainte jusqu'au 16 novembre 2005 à 18 heures.
C. Contre le jugement cantonal du 12 juin 2007, qui lui a été expédié sous pli recommandé du même jour, l'Office des poursuites de Martigny a interjeté, le (lundi) 25 juin 2007, un recours en matière civile. Il y invoque essentiellement la violation des art. 17 et 36 LP et conclut à ce que soient mis à la charge de la créancière, en plus des montants admis dans l'arrêt attaqué, divers frais totalisant 130'104 fr. (frais d'hôtel et d'immobilisation des chauffeurs à Bâle, indemnités de repas, argent remis aux convoyeurs pour assistance, frais téléphoniques, supplément de primes d'assurance pour les véhicules non climatisés immobilisés, factures de l'Office des poursuites de Bâle-Ville et de la police cantonale bâloise, frais additionnels du transporteur allemand Hasenkamp International Transports).
La créancière conclut au rejet du recours.

Le Tribunal fédéral considère en droit:
1. 1.1 Dirigé contre une décision rendue en matière de poursuite pour dettes et de faillite (<ref-law>) par une autorité cantonale de surveillance de dernière instance (<ref-law>), le recours est recevable indépendamment de la valeur litigieuse (art. 74 al. 2 let. c LTF). Il a en outre été déposé dans le délai (art. 100 al. 2 let. a en liaison avec l'<ref-law>) et la forme (<ref-law>) prévus par la loi.
1.2 Dès lors qu'il renvoie la cause à l'office pour nouvelle décision avec établissement d'un nouveau décompte de frais, le jugement attaqué est incident au sens de l'<ref-law>. Les exigences de cette disposition ayant été simplement reprises de l'ancien droit, en particulier des art. 50 al. 1 et 87 al. 2 OJ (cf. Message concernant la révision totale de l'organisation judiciaire fédérale du 28 février 2001, FF 2001 p. 4131 s.), il y a lieu d'admettre, conformément à la jurisprudence qui prévalait sous l'empire de l'ancien droit (<ref-ruling> consid. 1), qu'une décision de renvoi assortie, comme en l'espèce, d'injonctions très précises peut faire l'objet d'un recours au Tribunal fédéral en dépit de son caractère incident.
1.3 L'<ref-law> subordonne la recevabilité du recours en matière civile contre une décision en matière de poursuite pour dettes et de faillite (<ref-law>) à l'existence d'un intérêt juridique à l'annulation ou à la modification de la décision attaquée.
Comme sous l'ancien droit (<ref-law>, 78 ss OJ), un office des poursuites et faillites a qualité pour recourir malgré son absence d'intérêt juridique lorsque, comme en l'espèce, il agit comme organe du canton et fait valoir les intérêts du fisc, c'est-à-dire revendique que des frais soient assumés par une partie à la procédure de poursuite plutôt que par l'Etat (arrêt 5A_335/2007 du 13 décembre 2007 consid. 1.3, destiné à la publication).
Au vu de ce qui précède, il y a lieu d'entrer en matière.
2. Le recours en matière civile peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (cf. <ref-ruling> consid. 1.4 in fine, 297 consid. 3.1).
3. L'office recourant estime qu'on ne saurait lui faire grief de s'en être tenu à la règle, déduite de l'<ref-law>, selon laquelle la plainte LP ne bénéficie d'aucun effet suspensif de par la loi. C'est donc à tort, selon lui, que l'autorité cantonale de surveillance lui a reproché de ne pas avoir différé la levée de la saisie jusqu'à droit connu sur le dépôt éventuel d'une plainte et l'octroi de l'effet suspensif dans le cadre de celle-ci.
3.1 L'autorité cantonale supérieure de surveillance s'est référée à la pratique selon laquelle les organes de l'exécution forcée attendent généralement que le délai de plainte ou de recours soit échu ou qu'une décision ait été rendue sur l'effet suspensif avant d'exécuter une décision (<ref-ruling> consid. 2c p. 41; Flavio Cometta, Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, n. 10 ad <ref-law>; Pauline Erard, Commentaire romand de la LP, n. 11 ad <ref-law>). En l'espèce, a-t-elle constaté, la levée de la saisie des tableaux était de nature à causer un dommage irréparable à la créancière car, une fois hors de Suisse, ceux-ci devenaient insaisissables, de sorte que le dépôt d'une plainte à l'autorité inférieure de surveillance n'avait plus de raison d'être; l'office avait procédé dans l'urgence alors que rien ne le justifiait, le départ des tableaux ayant été planifié sur trois jours, du 15 au 17 novembre 2005; il avait donc pris le parti de rendre la plainte vaine et de causer un dommage irréparable à la créancière; en renonçant à surseoir à la levée de la saisie jusqu'au dépôt de la plainte et à la décision sur l'effet suspensif, il avait en conséquence commis une erreur d'appréciation et sa décision avait engendré des frais dus aux mesures conservatoires urgentes qu'il avait fallu mettre en oeuvre dans les cantons du Valais, de Bâle et de Genève pour récupérer les tableaux avant qu'ils ne quittent la Suisse, et ces frais ne pouvaient pas être mis à la charge de la créancière.
3.2 La pratique sur laquelle s'est fondée l'autorité cantonale implique que l'office ait la maîtrise sur l'exécution de sa décision. Ainsi, lorsque celui-ci décide de procéder à un acte de réalisation, une vente aux enchères publiques par exemple, il est en son pouvoir de différer l'exécution de cette décision jusqu'à droit connu sur une éventuelle plainte ou une requête d'effet suspensif. Tel n'est pas le cas lorsque l'office ordonne la levée d'une saisie, c'est-à-dire met fin à l'interdiction faite au débiteur de disposer des biens saisis sans son autorisation (<ref-law>; <ref-ruling> consid. 1 p. 69/70 et les arrêts cités), sa décision réintégrant ipso facto le débiteur dans son droit de disposition. Une telle décision n'implique donc en soi aucune exécution sur laquelle l'office aurait la maîtrise. Il suit de là que la pratique invoquée par l'autorité cantonale n'est pas pertinente en l'espèce.
3.3 Les mesures de sûreté au sens des <ref-law>, qui présupposent en principe une saisie valablement exécutée (<ref-ruling>), sans toutefois en constituer des éléments essentiels (P.-R. Gilliéron, Commentaire de la loi fédérale sur la poursuite pour dettes et la faillite, n. 42 ad <ref-law>; Nicolas de Gottrau, Commentaire romand de la LP, n. 2 ad <ref-law> et les références), tombent automatiquement avec la levée de la saisie. En l'occurrence, la mesure confiant au tiers détenteur la garde provisoire des biens saisis, à charge de les représenter en tout temps (<ref-law>), est donc devenue caduque au moment même de la levée de la saisie, l'avis au tiers détenteur n'ayant qu'un effet déclaratif.
La créancière intimée laisse entendre que l'office aurait pu différer l'avis donné au tiers détenteur. En informant précipitamment celui-ci de la levée de la saisie, il aurait procédé dans une urgence que rien ne justifiait et causé de la sorte l'enlèvement immédiat des tableaux et la course-poursuite onéreuse qui en a résulté. Cet argument ne résiste pas à l'examen déjà sous l'angle de la causalité. L'avis de levée de la mesure de sûreté donné par l'office au tiers détenteur à 13 h 12 n'a nullement été causal dans l'enlèvement des tableaux, car il est quasi certain que la débitrice, informée de la levée de la saisie juste avant le tiers détenteur (13 h 02), aurait, comme elle en avait d'ailleurs parfaitement le droit, fait enlever les tableaux avant l'octroi de l'effet suspensif (17 h 41) sur simple présentation de la décision de levée de la saisie, étant rappelé que cet enlèvement a effectivement eu lieu entre 13 h 48 et 14 h 39.
C'est dès lors à tort que l'autorité cantonale supérieure de surveillance a décidé de laisser les frais consécutifs à la levée de la saisie à la charge de l'office. Ces frais doivent être supportés, conformément à la règle, par la créancière intimée, responsable des dépenses liées à une requête dont elle a finalement été déboutée.
4. Il résulte de ce qui précède que le recours doit être admis et le jugement attaqué réformé dans la mesure où il laisse à la charge de l'office, partant de l'Etat, les frais consécutifs à l'annulation de la saisie dès le 15 novembre 2005 à 13 heures. Contrairement à ce que retient le jugement attaqué, ces frais doivent également comprendre la facture du transporteur allemand Hasenkamp International Transports de 42'164 fr. En effet, cette facture a manifestement été établie, comme le constate d'ailleurs elle-même l'autorité cantonale de surveillance, en raison de la saisie des tableaux sur le territoire suisse ("Return Martigny-Moscow, additional charges caused to temporary confiscation by the Swiss authorities"); elle concerne donc la procédure d'exécution forcée en cause. Le total des frais en question s'élève ainsi à 130'104 fr.
5. Les frais du présent arrêt doivent être mis à la charge de la créancière intimée, qui succombe (<ref-law>). Conformément à l'<ref-law>, il n'y a pas lieu d'allouer de dépens à l'office recourant.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et le jugement attaqué est réformé en ce sens que la créancière intimée est condamnée à supporter, en sus des frais déjà mis à sa charge, les frais consécutifs à l'annulation de la saisie dès le 15 novembre 2005 à 13 heures, à hauteur de 130'104 fr.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge de la créancière intimée.
3. Il n'est pas alloué de dépens.
4. Le présent arrêt est communiqué en copie aux mandataires des parties et au Tribunal cantonal du canton du Valais, Autorité supérieure de surveillance en matière de LP.
Lausanne, le 29 janvier 2008
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le président: Le greffier: