Fatti:
A. Nell'ambito di un procedimento penale aperto in Italia, la Procura della Repubblica presso il Tribunale di X._ ha chiesto il rinvio a giudizio, tra gli altri, di B._, A._ e C._ per il reato di concorso in corruzione per un atto contrario ai doveri d'ufficio (art. 110 e 319 del Codice penale italiano). Secondo l'autorità italiana, B._, consulente della D._S.p.A., e A._, imprenditore portuale e socio di B._, avrebbero concluso un accordo corruttivo con C._, allora sindaco di X._, per garantirsi un'importante commessa di carbone. Dalla prima metà del 2002, D._S.p.A. era infatti proprietaria della centrale termoelettrica di X._, alimentata a carbone, mentre B._ era agente per l'Italia della società E._Ltd a Singapore, che acquistava, per conto della D._S.p.A., dalle miniere indonesiane una qualità di carbone a basso contenuto di zolfo (denominato "Adaro"). La centrale termoelettrica in esercizio dal 1964 sarebbe stata destinata alla chiusura per la carenza di dispositivi di protezione ambientale, ma C._, dietro compenso, si sarebbe adoperato per mantenerla in esercizio in virtù del suddetto accordo corruttivo, garantendo la sottoscrizione della convenzione che prevedeva l'utilizzazione da parte di D._S.p.A. del carbone "Adaro" per la parziale alimentazione della centrale.
Con sentenza del 17 febbraio 2006 del Giudice per le indagini preliminari presso il Tribunale di X._, emanata secondo il rito del patteggiamento, B._ è stato condannato a una pena di un anno e cinque mesi di reclusione. L'accusato ha inoltre versato un importo di EUR 330'000.--, di cui il giudice ha disposto la confisca.
Con sentenza del 30 gennaio 2009 della seconda sezione penale del Tribunale di X._, A._ è stato condannato, anche per altri fatti che qui non interessano, alla pena di cinque anni di reclusione. Contro questo giudizio sia l'accusato sia il Pubblico ministero hanno interposto appello.
B. Con atto di accusa del 15 maggio 2009, il Ministero pubblico della Confederazione (MPC) ha messo in stato di accusa dinanzi al Tribunale penale federale (TPF) B._ e A._ per ripetuto riciclaggio di denaro aggravato giusta l'<ref-law>, in relazione ad atti, eseguiti essenzialmente su conti bancari in Svizzera, suscettibili di vanificare l'accertamento dell'origine, il ritrovamento o la confisca di valori patrimoniali derivanti dall'attività del commercio di carbone realizzata in base all'accordo corruttivo.
C. Con sentenza del 3 dicembre 2009, la Corte penale del TPF ha riconosciuto B._ colpevole di ripetuto riciclaggio di denaro, per avere operato o fatto operare tra il 12 marzo 2003 e il 20 ottobre 2003 trasferimenti di denaro dalla relazione bancaria yyy a favore della relazione bancaria zzz, entrambe presso la banca F._ di Lugano, per un valore complessivo di USD 265'576.05. L'accusato è stato condannato a una pena detentiva di un mese, sospesa condizionalmente per un periodo di prova di due anni, a valere quale pena complementare alla pena di un anno e cinque mesi di reclusione inflitta mediante la sentenza 17 febbraio 2006 del giudice italiano.
Nello stesso giudizio, A._ è stato riconosciuto colpevole del medesimo reato e di un ulteriore atto di riciclaggio di denaro, in relazione alla sostituzione del beneficiario del trust intestatario della citata relazione zzz, per un valore complessivo di USD 83'173.30. L'imputato è stato condannato alla pena di 210 aliquote giornaliere di fr. 410.-- ciascuna, per un totale di fr. 86'100.--, sospesa condizionalmente per un periodo di prova di due anni.
La Corte penale del TPF ha inoltre ordinato il dissequestro di un conto intestato a B._ e alla moglie presso la banca G._ di Lugano.
D. Il MPC impugna questa sentenza con un ricorso in materia penale al Tribunale federale, chiedendo in via principale di annullarla e di rinviare la causa alla Corte penale del TPF per un nuovo giudizio, tranne che per quanto riguarda i dispositivi concernenti le condanne degli imputati e le sospensioni condizionali delle rispettive pene. Il ricorrente, che formula pure ulteriori domande in via subordinata, fa valere la violazione del diritto federale e l'accertamento inesatto dei fatti.
E. La Corte penale del TPF comunica di non avere particolari osservazioni da presentare, rilevando che l'applicazione dell'art. 55 CAS, prospettata dal ricorrente, non entra in considerazione, siccome i fatti sono avvenuti in parte sul territorio italiano. A._ e B._ chiedono entrambi di respingere il ricorso.
F. Con decreto presidenziale del 1° aprile 2010 è stato conferito parziale effetto sospensivo al ricorso, nel senso che è stato mantenuto il sequestro del conto presso la banca G._ di Lugano. Preso atto dell'estinzione del conto intervenuta nel frattempo, con ulteriore decreto presidenziale del 29 aprile 2010, è stato ordinato il versamento su un conto del MPC dell'importo oggetto del sequestro.

Diritto:
1. Il ricorso, tempestivo e diretto contro una decisione finale (art. 100 cpv. 1 e 90 LTF) resa in materia penale (<ref-law>) dalla Corte penale del TPF (<ref-law>), è di massima ammissibile. La legittimazione del ricorrente è data (art. 81 cpv. 1 lett. b n. 3 LTF).
2. 2.1 Il ricorrente rimprovera alla precedente istanza una violazione del principio "ne bis in idem", segnatamente dell'art. 54 della Convenzione di applicazione dell'Accordo di Schengen del 14 giugno 1985 (CAS), per avere considerato che la ricezione di denaro da parte di C._, per il tramite di A._, sul conto aperto in Svizzera costituiva un fatto già assorbito dal reato di corruzione a monte.
2.2 Il principio "ne bis in idem" vieta che una persona sia perseguita penalmente due volte per gli stessi fatti; esso è violato quando sono identici l'oggetto del procedimento, la persona interessata e i fatti considerati (<ref-ruling> consid. 2b).
L'art. 54 CAS, invocato dal ricorrente, prevede che una persona che sia stata giudicata con sentenza definitiva in una Parte contraente non può essere sottoposta ad un procedimento penale per i medesimi fatti in un'altra Parte contraente a condizione che, in caso di condanna, la pena sia stata eseguita o sia effettivamente in corso di esecuzione attualmente o, secondo la legge dello Stato contraente di condanna, non possa più essere eseguita. Secondo l'art. 2 n. 1 dell'Accordo del 26 ottobre 2004 tra la Confederazione Svizzera, l'Unione europea e la Comunità europea, riguardante l'associazione della Svizzera all'attuazione, all'applicazione e allo sviluppo dell'acquis di Schengen (Accordo di associazione a Schengen; RS 0.362.31), in relazione con l'allegato A dell'Accordo, la Svizzera attua e applica l'art. 54 CAS. Essa ha inoltre dichiarato secondo l'art. 55 n. 1 CAS di non essere vincolata dall'art. 54 CAS quando, in particolare, i fatti oggetto della sentenza straniera sono avvenuti totalmente o in parte sul suo territorio; in quest'ultimo caso questa eccezione non si applica se i fatti sono avvenuti in parte sul territorio della Parte contraente in cui la sentenza è stata pronunciata.
2.3 Ora, l'eccezione dell'art. 55 n. 1 CAS invocata dal ricorrente non entra qui in considerazione dal momento che i fatti sono avvenuti in parte anche in Italia, in particolare per quanto concerne gli atti di corruzione. Sotto questo profilo è infatti determinante il complesso dei fatti tra di loro strettamente legati, indipendentemente dalla loro qualifica giuridica o dal bene giuridico protetto (cfr. sentenza della CGCE del 28 settembre 2006 nella causa C-150/05 Jean Leon Van Straaten, citata in: LAURENT MOREILLON, La coopération judiciaire pénale dans l'Espace Schengen, in: Aspects pénaux des Accords bilatéraux Suisse / Union européenne, 2008, pag. 515). La precedente istanza ha quindi esaminato a ragione se fossero dati "medesimi fatti" giusta l'art. 54 CAS.
Premesso che le fattispecie oggetto delle procedure appaiono di principio diverse, dal momento che il procedimento in Italia riguarda il reato di corruzione mentre quello in Svizzera concerne il reato di riciclaggio di denaro, la questione di sapere quali siano in concreto i singoli fatti posti alla base dei rispettivi procedimenti concerne il loro accertamento. Il ricorrente non censura tuttavia d'arbitrio gli accertamenti della precedente istanza, spiegando, con una motivazione conforme alle esigenze degli art. 42 cpv. 2 e 106 cpv. 2 LTF, perché e in quale misura essi sarebbero chiaramente in contrasto con gli atti e manifestamente insostenibili (cfr. sulle esigenze di motivazione, <ref-ruling> consid. 1.4.1 e rinvii). L'accertamento della precedente istanza, secondo cui i fatti giudicati in Italia comprendono le dazioni di denaro destinate a C._ versate sul conto yyy presso la banca F._ di Lugano, è quindi vincolante per il Tribunale federale (<ref-law>). Rientra del resto nel reato di corruzione ai sensi dell'art. 319 del Codice penale italiano, oltre all'accettazione della promessa di denaro, anche la ricezione dello stesso da parte del corrotto (cfr. CRESPI/ STELLA/ZUCCALÀ, Commentario breve al codice penale, complemento giurisprudenziale, 7a ed. 2004, pag. 1189 seg.). Peraltro, qualora si volesse seguire la tesi che sembra prospettare il ricorrente, secondo la quale i versamenti sul conto yyy dovrebbero essere oggetto anche del procedimento penale aperto in Svizzera, egli non spiega per quali ragioni questi fatti realizzerebbero contestualmente gli estremi del reato di riciclaggio di denaro ai sensi dell'<ref-law>. In tali circostanze, la censura sollevata non permette di concludere che la Corte penale del TPF ha in concreto violato il principio "ne bis in idem" e l'art. 54 CAS.
3. 3.1 Il ricorrente fa valere una violazione dell'<ref-law> lamentando il fatto che la precedente istanza ha considerato di origine criminale soltanto i valori patrimoniali destinati al corrotto e non anche quelli destinati ai corruttori. Sostiene che tutto il guadagno dei corruttori, ricavato dalla vendita del carbone nel periodo incriminato e transitato sul conto yyy, sarebbe provento di reato, siccome sarebbe collegato in un rapporto di causalità adeguata con il reato di corruzione.
3.2 Occorre quindi stabilire in che misura i valori patrimoniali conseguiti dagli accusati mediante il commercio di carbone, favorito dall'accordo corruttivo, possono essere considerati provento della corruzione e quindi possibili oggetto di riciclaggio.
Secondo l'<ref-law> commette riciclaggio di denaro ed è punito con una pena detentiva sino a tre anni o con una pena pecuniaria, chiunque compie un atto suscettibile di vanificare l'accertamento dell'origine, il ritrovamento o la confisca di valori patrimoniali sapendo o dovendo presumere che provengono da un crimine. La giurisprudenza ha in particolare posto l'accento sull'atto suscettibile di vanificare la confisca, atto che di per sé include anche quello suscettibile di vanificare l'accertamento dell'origine e il ritrovamento dei valori patrimoniali (<ref-ruling> consid. 3.3). Il comportamento è quindi punibile se è idoneo a compromettere la confisca del prodotto del crimine.
Giusta l'<ref-law>, il giudice ordina la confisca segnatamente dei valori patrimoniali che costituiscono il prodotto di un reato. Nell'ambito di sentenze in materia di confisca, in applicazione del previgente art. 59 n. 1 cpv. 1 vCP, sostanzialmente corrispondente all'<ref-law>, il Tribunale federale ha rilevato che il reato deve essere la causa essenziale ed adeguata dell'ottenimento dei valori patrimoniali e che questi devono provenire tipicamente dal reato in questione. Deve quindi esistere, tra il reato e l'ottenimento dei valori patrimoniali un nesso causale tale da fare apparire il secondo come la conseguenza diretta e immediata del primo. È in particolare questo il caso, quando l'ottenimento dei valori patrimoniali costituisce un elemento oggettivo o soggettivo del reato o quando rappresenta un vantaggio diretto derivante dalla commissione dell'infrazione. Per contro, i valori patrimoniali non possono essere considerati come il risultato del reato, quando quest'ultimo ha soltanto facilitato il loro ottenimento ulteriore mediante un atto successivo senza connessione immediata con il reato stesso (cfr. sentenza 6S.667/2000 del 19 febbraio 2001 consid. 3a, in: SJ 2001 I 330; sentenza 6S.819/1998 del 4 maggio 1999 consid. 2a, in: SJ 1999 I 417). Il Tribunale federale aveva al riguardo richiamato in particolare il commentario edito da NIKLAUS SCHMID, Kommentar Einziehung, Organisiertes Verbrechen, Geldwäscherei, vol. I, 1998 (cfr. NIKLAUS SCHMID, op. cit., n. 30 e 34 segg. all'<ref-law>; cfr. inoltre, nella stessa opera, JÜRG-BEAT ACKERMANN, n. 164 all'<ref-law>).
Trattandosi in particolare di redditi derivanti da negozi giuridici resi possibili grazie alla corruzione, il primo degli autori succitati aveva negato ch'essi potessero essere qualificati quali "valori patrimoniali che costituiscono il prodotto di un reato" e che potessero quindi essere confiscati, mancando un rapporto diretto tra il reato e il vantaggio economico conseguito (cfr. SCHMID, op. cit., n. 36 all'<ref-law>, pag. 102). In considerazione del mutato quadro legale, questo autore ha tuttavia rivisto e precisato questa opinione nella seconda edizione dell'opera citata, in cui non esclude che possa anche essere sostenuta la tesi contraria, purché la confisca sia limitata alla parte di profitto riconducibile alla corruzione sulla base di un nesso causale dimostrato (cfr. SCHMID, op. cit., 2a ed., 2007, n. 36a segg. agli art. 70-72 CP). Questa soluzione è sostenuta dalla dottrina più recente, che ammette di massima la possibilità di una confisca di valori patrimoniali conseguiti in esecuzione di un contratto ottenuto in rapporto di causalità adeguata mediante un atto corruttivo (cfr. BERNARD BERTOSSA, Confiscation et corruption, in: SJ 2009 II 371 pag. 378; cfr. inoltre BERTRAND PERRIN, La répression de la corruption d'agents publics étrangers en droit pénal suisse, 2008, pag. 272 seg.; DANIEL JOSITSCH, Das Schweizerische Korruptionsstrafrecht, 2004, pag. 425 seg. e 428; MARK PIETH, Korruptionsgeldwäsche, in: Wirtschaft und Strafrecht; Festschrift für Niklaus Schmid, 2001, pag. 448 seg.). A ragione la precedente istanza vi ha quindi fatto esplicito riferimento nel suo giudizio, esaminando sotto questo profilo la questione di sapere se il vantaggio (indiretto) conseguito dai corruttori proveniva da un crimine e poteva quindi essere oggetto di riciclaggio giusta l'<ref-law>. Alla luce di queste considerazioni, l'esposta giurisprudenza del Tribunale federale deve quindi essere precisata nel senso che, per essere considerati prodotto di reato, i valori patrimoniali ottenuti da un negozio giuridico conseguito mediante la corruzione devono stare in un rapporto causale naturale ed adeguato con il reato, senza che siano necessariamente la conseguenza diretta ed immediata dello stesso.
3.3 In concreto, il semplice fatto che i vantaggi patrimoniali conseguiti dagli accusati provenivano dal commercio del carbone e derivavano quindi soltanto indirettamente dall'accordo corruttivo non basta perciò a negare che possano essere considerati come provenienti da un crimine. Come visto, neppure la precedente istanza ha preteso il contrario, ma ha rettamente richiesto l'esistenza di una causalità adeguata.
Al riguardo, i primi giudici hanno rilevato che non era sufficientemente dimostrato un nesso causale tra la corruzione del sindaco C._ e i valori patrimoniali conseguiti dagli accusati mediante il commercio del carbone destinato alla centrale termoelettrica di X._. Hanno in particolare ritenuto che non era provato, "che in assenza di tale accordo corruttivo i gruppi funzionanti a carbone della centrale termoelettrica di X._ sarebbero stati chiusi, rispettivamente che la centrale non sarebbe stata rifornita col carbone Adaro atteso che questa soluzione è stata comunque adottata sulla base di parallele sentenze del TAR e del Consiglio di Stato e continua tuttora ad essere adottata a X._ nonostante sia notorio a tutti quanto è successo intorno al sindaco C._". La Corte penale del TPF si è invero chiesta "se ciò sarebbe avvenuto anche senza l'accordo tra C._ e gli accusati nella misura in cui tale accordo ha dato l'abbrivio, limitando per una certa inevitabile inerzia le successive possibilità di scelta della D._S.p.A. di approvvigionarsi in carbone presso altri fornitori o comunque di guardarsi in giro alla ricerca di altre soluzioni". Poiché non erano stati apportati sufficienti indizi sul rapporto di causalità, la Corte penale non ha però esaminato oltre la questione ed ha per finire negato che i valori patrimoniali di spettanza degli accusati derivanti dal commercio del carbone potessero essere considerati di origine criminale ai sensi dell'<ref-law>.
Il ricorrente sostiene che la precedente istanza avrebbe negato a torto il nesso causale tra i valori patrimoniali ottenuti dagli opponenti e l'accordo corruttivo, ma non si confronta con queste considerazioni. Nemmeno tiene conto degli accertamenti relativi all'esistenza delle decisioni sia del Tribunale amministrativo regionale sia del Consiglio di Stato e al mantenimento dell'approvvigionamento in carbone "Adaro" malgrado la notorietà delle vicende che hanno coinvolto il sindaco. Non fa in particolare valere, con una motivazione conforme alle esigenze di motivazione degli art. 42 cpv. 2 e 106 cpv. 2 LTF, che questi accertamenti sarebbero manifestamente insostenibili o chiaramente in contrasto con gli atti, né spiega per quali ragioni, nonostante le considerazioni dei primi giudici, un rapporto causale dovrebbe comunque essere ammesso o non sarebbe venuto meno.
Certo, nel giudizio impugnato (consid. 4.1.1), i primi giudici danno un peso rilevante alla corruzione del sindaco nell'ottica del mantenimento in esercizio della centrale. Inoltre, le decisioni del Tribunale amministrativo regionale e del Consiglio di Stato sembrano concernere unicamente una domanda incidentale di sospensione dell'esecuzione dell'ordine di chiusura disposto dal sindaco. Tuttavia, il ricorrente adduce in sostanza solo che l'esistenza dell'accordo corruttivo risulterebbe dalle sentenze emanate nell'ambito del procedimento italiano e sarebbe ammessa dagli stessi accusati. Non sostanzia, con chiarezza e precisione, che le considerazioni della precedente istanza sulle decisioni del Tribunale amministrativo regionale (TAR) e del Consiglio di Stato e sulla loro rilevanza sarebbero manifestamente in contrasto con specifiche constatazioni risultanti dai giudizi italiani. Né egli sostiene che, anche tenendo conto di questi elementi, avrebbe dimostrato che la corruzione del sindaco costituirebbe la condizione per la fornitura del carbone alla centrale, attività commerciale che ha permesso in ultima analisi agli accusati di realizzare gli utili in discussione. Le argomentazioni ricorsuali non consentono quindi di concludere che i primi giudici hanno violato l'<ref-law> ritenendo che tali valori patrimoniali non potevano essere considerati come provento di crimine.
4. 4.1 Il ricorrente rimprovera inoltre alla precedente istanza di avere negato a torto l'esistenza di un caso grave di riciclaggio secondo l'art. 305bis n. 2 lett. c CP. Sostiene, che in concreto sarebbero realizzati gli estremi dell'aggravante del mestiere, siccome il reato sarebbe legato all'attività imprenditoriale svolta dagli accusati a titolo professionale. Il loro guadagno sarebbe inoltre considerevole e corrisponderebbe agli importi giunti sui conti in Svizzera, che rappresenterebbero la loro fonte principale di reddito.
4.2 È dato un caso grave ai sensi dell'invocata disposizione, se l'autore realizza una grossa cifra d'affari o un guadagno considerevole facendo mestiere del riciclaggio. Come rettamente rilevato dalla Corte penale del TPF, l'autore agisce per mestiere, quando dal tempo e dai mezzi consacrati all'attività delittuosa, dalla frequenza degli atti durante un periodo determinato, come pure dai redditi prospettati od ottenuti risulta ch'egli esercita tale attività alla stregua di una professione, quand'anche accessoria. Occorre, che l'autore aspiri ad ottenere dei redditi relativamente regolari, che rappresentino un apporto notevole al finanziamento del suo stile di vita, e che si sia così in un certo modo installato nella delinquenza (<ref-ruling> consid. 2.1). Inoltre, ai sensi dell'art. 305bis n. 2 lett. c CP, è da considerarsi grossa una cifra d'affari di fr. 100'000.-- o più (<ref-ruling> consid. 3.1.1) e considerevole un guadagno di almeno fr. 10'000.-- (<ref-ruling> consid. 2.2).
4.3 Ora, il ricorrente motiva la censura partendo dal presupposto che tutto l'utile ricavato dalla vendita del carbone transitato sul conto yyy costituirebbe provento di reato. Come visto, la precedente istanza si è invece fondata su una fattispecie diversa, ravvisando il reato di riciclaggio unicamente nei trasferimenti del denaro di spettanza del corrotto dal conto yyy al conto zzz eseguiti tra il 12 marzo 2003 e il 20 ottobre 2003. Comunque, essa non ha violato l'art. 305bis n. 2 lett. c CP negando un caso grave ai sensi di questa disposizione, siccome ha rettamente rilevato che l'importo conseguito non era stato realizzato mediante l'attività di riciclaggio in quanto tale.
5. Il ricorrente si diparte da una fattispecie diversa da quella accertata anche laddove contesta il dissequestro della relazione bancaria intestata a B._ e alla moglie. Richiama peraltro genericamente gli art. 70 e 71 CP, prospettando una "confisca a titolo di risarcimento equivalente" dei valori patrimoniali depositati. Non si confronta tuttavia puntualmente, con una motivazione conforme alle esigenze dell'<ref-law>, con il considerando 11.2 della sentenza impugnata, in cui i giudici hanno negato, spiegandone le ragioni, sia i requisiti di una confisca sia quelli di un risarcimento equivalente. La critica, inammissibile, non deve pertanto essere esaminata oltre.
6. Ne segue che il ricorso deve essere respinto nella misura della sua ammissibilità. Non si prelevano spese giudiziarie a carico del ricorrente, che si è rivolto al Tribunale federale nell'esercizio delle sue attribuzioni ufficiali (<ref-law>). La Confederazione verserà agli opponenti un'indennità a titolo di ripetibili di questa sede (<ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. Non si prelevano spese giudiziarie.
3. La Confederazione verserà a ciascun opponente un'indennità di fr. 3'000.-- a titolo di ripetibili di questa sede.
4. Comunicazione alle parti, rispettivamente ai loro patrocinatori, e alla Corte penale del Tribunale penale federale.