I have heard of four (attempted) solutions to this, and none of them is perfect:
1. Gateways (à la Ripple)
Though exchanges themselves are decentralised, the "coloured coins" they exchanged need to be issued by a trusted (centralised) authority who will exchange for example 10EUR/USD for 10cEUR/cUSD which can THEN be exchanged for BTC or other currencies.
2. IOUs (à la Ripple)
Rather than trading actual currencies, people make interest-free "loans" and trade the debt. For example, you give me 1BTC for a 150GBP "IOU", which you can trade on to other people with the promise that I (or others trading IOUs in the same currency) will buy it back for 150GBP worth of BTC/some other currency. Of course this relies on people having confidence they will be able to trade the IOUs back to Bitcoins.
3. Magic (à la Harry Potter)
Some sort of coloured coins are distributed that by convention just happen to be pegged exactly to EUR/USD/GBP or whatever, and eventually the convention becomes so universal that people stop distinguishing between cEUR and EUR.
4. Automatic "monetary policy" (à la Mastercoin)
One suggestion I have seen, I think it might have been for Mastercoin but I'm not 100% sure, was that some sort of decentralised "system address" would hold an excess of for example cEUR, and when the BTC value of cEUR started to climb above EUR more cEUR would be released into the market, and if the value was below EUR then the system would buy back some cEUR for BTC to bring the value back up. How the system would track the value of the EUR however I don't know. Presumably it would be a mathematical system not relying on external feedback, so would try to approximate a certain value that was equal to the value of the EUR at the time of implementation, which obviously could change over time and the correlation become broken.