Bitcoin from different inputs are completely mixed in a transaction. Assuming that Alice has 1 Red coin in a single output, and Bob has 5 Blue coins in a single output. To buy the Red coin from Alice, Bob will pay 1 Blue coin + 5BTC. Bob will also pay the transaction fee.
Input
1. Address A (Red coins): 1BTC (Alice)
2. Address B (Blue coins): 5BTC (Bob)
3. Address C (Normal bitcoin): 10.005BTC (Bob)
Output
1. Address D: 1BTC (Bob)
2. Address E: 4BTC (Bob)
3. Address F: 1BTC (Alice)
3. Address G: 5BTC (Alice)
4: Address H: 5BTC (Bob)
Transaction fee: 0.005BTC
Presumably, the 1BTC in Address D should be a Red coin, and the 1BTC in Address F should be a Blue coin. The 4BTC in Address E is a "change" from Address B and are Blue coins. The 5 BTC in Address G is the payment in normal bitcoin, and the 5BTC in Address H is the change of normal bitcoin going back to Bob.
The question is, since bitcoin is fungible, how do we know the color of these coins?
Furthermore, if someone mixes 1 Red coin and 2 Blue coins and makes a single output of 3BTC, what is the color of the output?
How about paying transaction fee with colored coins? Will the miner claim it with the coinbase input?
I understand the coloring part, but I don't get how this paves the way for distributed exchanges. What am I missing?
People having coins of different colors can exchange them securely via a simple bitcoin transaction which would be atomic.
E.g. one person gives 1 red coin and gets 5 blue coins, other person gives 5 blue coins and gets 1 red coins, they construct a transaction, sign it, and once it is in blockchain trade is done. (If one person signs but other doesn't transaction would be invalid. If there is a double-spend, it would also invalidate whole txn. So trade transactions are in fact more secure than accepting bitcoins.)
So what's left is order matching logic, i.e. allowing person which is willing to trade red coins for blue coins to find a person who wants the opposite.
This is fairly simple to implement and straightforward.