Fatti:
A. Il 3 luglio e il 4 novembre 2003 la Direzione generale delle dogane a Berna, informata a sua volta dal Ministero pubblico del Cantone di Basilea Città, ha segnalato al Ministero pubblico della Confederazione una sospetta importazione di orologi di lusso, in particolare di un orologio della marca Piaget, da parte di un cittadino straniero residente in Svizzera. L'autorità doganale ha inoltre segnalato di avere sequestrato, presso la residenza di quest'ultimo a Kaiseraugst, sia il citato orologio sia un documento redatto in spagnolo su supporto informatico concernente un'attività di riciclaggio mediante il commercio di orologi di lusso.
Il Ministero pubblico della Confederazione ha avviato un'indagine di polizia giudiziaria contro ignoti per il titolo di riciclaggio di denaro e ordinato, il 13 novembre 2003, la perquisizione e il sequestro dell'orologio Piaget depositato presso la Direzione generale delle dogane e della documentazione relativa all'incasso del dazio d'importazione e all'accertamento della proprietà dell'orologio.
B. Contro l'ordine di perquisizione e di sequestro A._, presunto proprietario dell'orologio, è insorto il 1° marzo 2004 dinanzi alla Camera d'accusa del Tribunale federale chiedendo l'annullamento del provvedimento. Faceva essenzialmente valere di avere acquistato regolarmente l'orologio litigioso, di non essere in relazione con la persona che l'ha importato irregolarmente in Svizzera e di essere estraneo al prospettato reato di riciclaggio; censurava inoltre il diniego di consultare gli atti del procedimento. L'interessato criticava anche il fatto che il Ministero pubblico della Confederazione aveva condotto la procedura in italiano, nonostante l'assenza di qualsiasi relazione della fattispecie con la Svizzera italiana.
C. La Corte dei reclami penali del Tribunale penale federale, che ha ripreso la causa dopo l'entrata in vigore completa, il 1° aprile 2004, della legge sul Tribunale penale federale, ha accolto il gravame con sentenza del 27 maggio 2004. Ha rilevato che l'utilizzo della lingua italiana non aveva pregiudicato il reclamante nella procedura penale e che, visto lo stadio iniziale in cui si trovava il procedimento, un più ampio acceso agli atti non si giustificava. Ha inoltre ritenuto che le diverse fatture presentate dall'opponente concordavano riguardo alla sua identità quale acquirente e, quindi, proprietario dell'orologio, per il cui furto questi aveva d'altra parte sporto una denuncia penale in Messico. Ha constatato che non risultava dagli atti che il reclamante intratteneva relazioni con le persone indagate in Svizzera, segnatamente con l'importatore di orologi di lusso sospettato di riciclaggio. La Corte dei reclami penali ha quindi considerato che, nelle esposte circostanze, nonostante l'opponente soggiornasse all'estero, il mantenimento del sequestro non si giustificava. Ha ricordato che, peraltro, nella misura cui fossero pagate le tasse doganali, nemmeno la Direzione generale delle dogane avversava il dissequestro ed ha concluso che l'orologio doveva essere restituito all'opponente.
D. Il Ministero pubblico della Confederazione impugna con ricorso del 28 giugno 2004 al Tribunale federale questo giudizio, chiedendo di annullarlo e di mantenere l'ordine di sequestro del 13 novembre 2003. Postula inoltre il conferimento dell'effetto sospensivo. Ritiene i sospetti di reato nei confronti dell'importatore di orologi di lusso avvalorati in particolare dalla sua situazione finanziaria e dal contenuto dei dati elettronici rinvenuti presso la sua abitazione. Contestando partitamente le argomentazioni contenute nel giudizio impugnato, rileva inoltre come la pretesa estraneità dell'opponente ai fatti e la sua asserita proprietà dell'orologio sequestrato, ammessi dalla Corte dei reclami penali, non troverebbero riscontro negli atti.
E. La Corte dei reclami penali rinuncia a presentare osservazioni e si rimette al giudizio del Tribunale federale. L'opponente chiede, in via principale, di dichiarare inammissibile il ricorso e, in via subordinata, di respingerlo. Chiede inoltre di respingere la domanda di effetto sospensivo contenuta nel gravame.

Diritto:
1. 1.1 Secondo l'art. 33 cpv. 3 lett. a della legge del 4 ottobre 2002 sul Tribunale penale federale (LTPF; RS 173.71), fino all'entrata in vigore della revisione totale dell'OG, le decisioni della Corte dei reclami penali concernenti misure coercitive sono impugnabili mediante ricorso al Tribunale federale entro 30 giorni dalla notifica, per violazione del diritto federale; la procedura è retta dagli art. 214-216, 218 e 219 della legge federale sulla procedura penale (PP; RS 312.0), applicabili per analogia.
1.2 La decisione oggetto del ricorso, relativa a un ordine di perquisizione e di sequestro e quindi a una misura coercitiva (messaggio del Consiglio federale concernente la revisione totale dell'organizzazione giudiziaria federale, del 28 febbraio 2001, FF 2001 p. 3764, n. 2.2.3 pag. 3793), è di principio impugnabile dinanzi al Tribunale federale. Nella sentenza 130 I 234, è stata riconosciuta al Ministero pubblico della Confederazione, quale parte nella procedura penale federale, la legittimazione a ricorrere in questa sede contro l'annullamento da parte del Tribunale penale federale di misure coercitive ordinate dall'Ufficio dei giudici istruttori federali. È tuttavia stata lasciata indecisa la questione di sapere se esso potrebbe perderla quando l'oggetto del litigio è, come in concreto, una decisione da lui stesso emanata (cfr. <ref-ruling> consid. 3.1 pag. 237). Ora, secondo l'art. 214 cpv. 2 PP, applicabile per analogia (cfr. l'art. 33 cpv. 3 lett. a LTPF), il diritto di ricorrere spetta segnatamente alle parti, tra le quali, nella procedura penale federale, rientra esplicitamente il procuratore generale (cfr. art. 34 PP). La direzione delle indagini preliminari compete del resto a quest'ultimo (cfr. art. 104 cpv. 1 PP), che, in quanto titolare dell'azione penale, ha di principio un interesse all'esito della procedura e quindi anche all'annullamento di una decisione che la riguarda. Questo interesse deve essere riconosciuto anche quando, come nel caso, la Corte dei reclami penali annulli una misura coercitiva ordinata dal Ministero pubblico medesimo nell'ambito di indagini preliminari. Il riconoscimento della legittimazione a ricorrere in questa sede, si giustifica quindi anche in una fattispecie come quella in esame: il gravame, tempestivo, deve pertanto essere vagliato nel merito.
1.3 Secondo l'art. 37 cpv. 3 OG la sentenza del Tribunale federale è redatta in una lingua ufficiale, di regola in quella della decisione impugnata, che in concreto era la lingua italiana. Anche questo giudizio viene quindi redatto in italiano, nonostante la risposta dell'opponente sia stesa in francese (<ref-ruling> consid. 2; sentenza 1P.693/ 2001 del 16 gennaio 2002, consid. 1, pubblicata in RDAT I-2002, n. 41, pag. 296). Il rifiuto del Ministero pubblico di utilizzare la lingua tedesca nei rapporti con il precedente patrocinatore dell'opponente non è qui litigioso. La Corte dei reclami penali ha invero confermato questo diniego sulla base dell'art. 37 cpv. 3 OG. Ricordato che questa disposizione non disciplina direttamente tale questione, ma regola innanzitutto la lingua nella quale sono redatte le sentenze del Tribunale federale, si può rilevare che spettava in concreto al Ministero pubblico della Confederazione tenere conto, nel procedimento penale, dei legami linguistici con il luogo del sequestro e della lingua nazionale conosciuta ed utilizzata dagli interessati e non semplicemente sceglierne una a sua discrezione o secondo sue esigenze organizzative interne (cfr. <ref-ruling> consid. 5c).
1.4 Il procedimento in esame verte essenzialmente sulla pretesa violazione del diritto federale, segnatamente per quanto concerne i presupposti del sequestro (cfr. art. 65 segg. PP). Il presente giudizio non si fonda quindi su documenti del procedimento penale che l'opponente non ha (finora) potuto consultare, sicché la sua richiesta di estrometterli dall'incarto diviene priva d'oggetto.
2. 2.1 Il ricorrente sottolinea l'esistenza di sospetti di riciclaggio di denaro, fondati essenzialmente sulla carenza di disponibilità finanziaria dell'indagato in detto procedimento per gestire un commercio simile a quello da questi asseritamente praticato e sulla documentazione rinvenuta in occasione della perquisizione presso la sua abitazione. Rileva inoltre la necessità di eseguire ulteriori indagini anche riguardo all'accertamento della proprietà dell'orologio. Secondo il Ministero pubblico della Confederazione apparirebbe pure sospetto il fatto che l'orologio in questione, pagato secondo l'opponente US $ 250'000.--, sia stato acquistato in modo inusuale, allestendo diverse fatture, di diverso importo e prive di indicazioni riguardanti le modalità di consegna e di pagamento; tanto più che dagli atti risultano valori di stima di almeno fr. 600'000.-- e fino a fr. 1'076'000.--. Il ricorrente evidenzia poi l'esistenza di un rapporto di fiducia tra l'indagato e l'opponente e considera il provvedimento litigioso proporzionato anche tenuto conto del domicilio in Messico del secondo, che renderebbe ardua un'eventuale futura confisca dell'orologio. Ritiene infine che il giudizio impugnato, considerato che non risulterebbe pagata la multa doganale, doveva comunque ristabilire la situazione precedente l'adozione del sequestro penale e prevedere quindi la restituzione dell'oggetto alla Direzione generale delle dogane e non direttamente all'opponente.
2.2 Secondo l'art. 65 cpv. 1 PP gli oggetti che possono avere importanza come mezzi di prova devono essere sequestrati e posti in luogo sicuro o contrassegnati. Il loro detentore è tenuto a consegnarli a richiesta dell'autorità competente. Parimenti si possono sequestrare oggetti e beni patrimoniali sottostanti presumibilmente a confisca.
Il sequestro è un provvedimento processuale di natura cautelare, destinato ad assicurare temporaneamente mezzi probatori come pure gli oggetti ed i valori patrimoniali presumibilmente sottoposti a confisca. Presupposto del sequestro è l'esistenza di sufficienti, oggettivi e concreti sospetti di reato nei confronti del detentore dell'oggetto o di un terzo. Al riguardo non occorre tuttavia porre delle esigenze troppo severe se l'inchiesta penale si trova nella sua fase iniziale. Diversamente dal giudice di merito, al Tribunale federale non incombe infatti eseguire a questo stadio del procedimento un'esauriente ponderazione delle circostanze a carico o a discolpa degli indagati e intraprendere una valutazione completa dell'attendibilità dei vari mezzi probatori disponibili. Occorre invece vagliare se l'autorità federale poteva ammettere l'esistenza di sufficienti e concreti indizi di reato (<ref-ruling> consid. 4, 122 IV 91 consid. 4, 125 IV 222 consid. 2c inedito).
2.3 La Corte dei reclami penali ha sostanzialmente fondato l'annullamento del provvedimento cautelare sull'estraneità dell'opponente ai fatti dell'inchiesta, sulla circostanza ch'egli avrebbe sufficientemente dimostrato la sua proprietà dell'orologio e sull'inesistenza, risultante dagli atti, di relazioni dell'opponente con l'importatore di orologi di lusso indagato in Svizzera per sospetto riciclaggio.
L'opponente medesimo ha tuttavia ammesso dinanzi all'autorità inquirente del Cantone di Basilea Città di conoscere l'indagato, con il quale intratteneva rapporti commerciali; nei suoi allegati di causa egli ha inoltre riconosciuto di avergli in precedenza già consegnato l'orologio litigioso per farlo periziare dal fabbricante Piaget, a Ginevra. In tali circostanze, l'accertamento secondo cui l'opponente non avrebbe intrattenuto relazioni con il principale indagato contrasta effettivamente con gli atti ed è quindi errato. Questa circostanza avrebbe suggerito alla precedente istanza di non attribuire un peso troppo rilevante alla denuncia per furto dell'opponente contro l'indagato, introdotta oltretutto dopo quattro mesi dal preteso reato. Comunque, nemmeno l'eventuale estraneità dell'opponente ai fatti incriminati è di per sé determinante nell'ambito dell'adozione della misura provvisionale, l'esistenza di sospetti di reato potendo, come visto, riferirsi sia al detentore dell'oggetto sia ad un terzo (<ref-ruling> consid. 4). Per giustificare tale provvedimento, occorre che sussistano ragionevoli motivi per ritenere che il bene sequestrato si identifichi con quello pervenuto all'interessato quale frutto di un reato (<ref-ruling> consid. 4); a questo stadio della procedura, non essendo (ancora) in discussione un'eventuale confisca, la questione della proprietà dell'orologio non è decisiva. Pertanto il fatto che l'opponente, secondo la precedente istanza, sarebbe il legittimo proprietario dell'orologio, non invalida di per sé la relazione dell'oggetto stesso con il reato di cui l'indagato è sospettato. Al proposito, il richiamo della Corte dei reclami penali a <ref-ruling> consid. 1b non appare pertinente, poiché tale sentenza concerne le conseguenze del dissequestro e indica i criteri per la restituzione dell'oggetto quando la titolarità del diritto reale sullo stesso è litigiosa.
Il giudizio impugnato fa essenzialmente riferimento alla segnalazione 4 novembre 2003 della Direzione generale delle dogane al Ministero pubblico, dalla quale risulta che l'autorità doganale ritiene sufficientemente dimostrato il diritto di proprietà dell'opponente, soprattutto sulla base delle diverse fatture da lui presentate, univoche quanto alla sua identità. Tuttavia, il fatto che per tali motivi la Direzione delle dogane non consideri più giustificato il provvedimento cautelare dal profilo del diritto doganale, non comporta d'acchito l'infondatezza del sequestro penale ordinato dal Ministero pubblico della Confederazione nel quadro di un'inchiesta retta dalla PP. Ora, la presentazione di tre differenti fatture per il medesimo oggetto, redatte in modo generico, con altre date e diversi prezzi, di US $ 250'000.-- (in un caso) e di US $ 210'000.-- (negli altri due casi), può apparire sospetta, ove si consideri il possibile rilevante valore dell'orologio (fr. 1'076'000.-- secondo lo stesso fabbricante Piaget). Queste circostanze poco chiare, valutate considerando sia l'attività di importazione illegale di orologi di lusso svolta dall'indagato, sia gli ulteriori articoli del genere e gli scritti rinvenuti presso il suo domicilio, permettono di ritenere sufficienti i sospetti di reato e giustificato quindi il sequestro. Ciò anche in considerazione del fatto che l'inchiesta penale si trova in uno stadio iniziale e che una più approfondita delucidazione della fattispecie necessita certamente di ulteriori indagini ed approfondimenti.
Il provvedimento cautelare, anche immobilizzando temporaneamente un valore patrimoniale dell'opponente, non gli impedisce di continuare a svolgere la sua attività commerciale e non pregiudica quindi irreparabilmente i suoi interessi professionali. Ritenuto altresì il suo domicilio all'estero, la criticata misura appare per finire rispettosa anche del principio della proporzionalità.
2.4 Va infine rilevato che, in concreto, il sequestro penale è stato ordinato dal Ministero pubblico della Confederazione presso la Direzione generale delle dogane, ove l'orologio Piaget era depositato e, in particolare, trattenuto a titolo di pegno doganale secondo l'art. 120 segg. della legge federale sulle dogane (LD; RS 631.0). Dalla segnalazione dell'Autorità doganale non risulta tuttavia chiaramente che gli obblighi doganali sarebbero stati nel frattempo estinti, né che un ricorso contro il sequestro del pegno doganale non sarebbe pendente (cfr. <ref-law>). In tali circostanze, mancando precisi accertamenti sull'eventuale necessità di trattenere ulteriormente l'orologio quale garanzia doganale, l'annullamento del sequestro penale non giustificava comunque la restituzione dell'oggetto direttamente nelle mani dell'opponente, come stabilito nel consid. 5 del giudizio impugnato.
3. Ne segue che il ricorso, fondato, deve essere accolto e la decisione impugnata annullata. Le spese seguono la soccombenza e sono quindi poste a carico dell'opponente (art. 156 cpv. 1 OG). Non si assegnano ripetibili all'autorità vincente (art. 159 cpv. 2 OG).
L'emanazione del presente giudizio rende priva di oggetto la domanda di effetto sospensivo.

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso è accolto e la decisione impugnata annullata.
2. La tassa di giustizia di fr. 2'000.-- è posta a carico dell'opponente.
3. Comunicazione al ricorrente, al patrocinatore dell'opponente e alla Corte dei reclami penali del Tribunale penale federale.