For such a scheme to work, if I have some currency, I have to be able to give it to Abel and I have to be able to give it to Beth, but I have to be unable to give it to both Abel and Beth. This means that giving the currency to Abel has to somehow make me unable to give the currency to Beth even though I previously could do that.
There are three mechanisms by which this can be accomplished:
There can be a central authority. To give the coins to Abel, I must tell the central authority that I have done so. The central authority would then prohibit me from giving the coins to Beth. This means giving coins requires both approval from the central authority and reporting to the central authority.
There can be a distributed secure device. To give the coins to Abel, I must tell the instance of the secure device that holds the coins. The device will then prohibit me from giving the coins to Beth once it has given them to Abel. This means coins must be held in a physically-secure device. In practice, it also requires a central authority to load the devices and issue keys to them. (I need to prove a secure device was involved in the transaction, which requires the device to have a certificate, which requires some authority to issue such certificates.)
At least some aspect of all transactions can be public. Thus, if I give the coins to Abel, there will be a record Beth can easily find. Beth will know the coins are not mine to give.
Bitcoin chooses the third approach. This seems the best approach for cryptographic decentralized currencies. There is no fourth approach known.
Now, the only information about the transaction that needs to be public is enough information to prove I have the coins and prove that I didn't transfer them elsewhere. As it happens, the Bitcoin protocol leaks much more information than this (for example, the account I transferred the coins to). The protocol could have been designed to make less information public if that was desired.
The coins need be traceable back to their origin. But whether or not you can track the particular accounts they passed through is an implementation decision.
For example, a hypothetical coin could use the following mechanism: Alice wants to send some coins to Bob. She knows Bob's public key. She generates a random private key just for this transaction and encrypts it with Bob's public key. She then publishes a transaction transferring coins to the public corresponding to the random private key she generated along with the encrypted version of that same key that she encrypted with Bob's public key.
Now, Bob will see a transaction that his private key is able to claim. Nobody else will know the transaction was to Bob because neither Bob's public key nor any analog of it appear in the block chain. Bob will have no idea the coins came from Alice and nobody else will have any idea the coins went to Bob.
This method still leaves the coins fully traceable. But no traceable accounts ever appear in the block chain.
This solves two 'problems' with Bitcoin. If I publish a bitcoin address somewhere, anyone can see how many Bitcoins that account got. If someone wants to transfer me bitcoins that cannot be traced, he must obtain a one-time use account from me, which he cannot easily do if he wishes to give me the coins anonymously.
You can still generate and use one-time accounts with Bitcoin, but you cannot broadcast them or they cease to be one-time accounts. And there is no easy way for someone to anonymously request one from you.
You might think this means every account must be tested to claim every transaction, resulting in an inefficient scheme and making things like web-based mass wallets computationally impractical. However, I've discovered a truly marvelous solution to this problem, but this answer is already too long.