I've seen a number of new exchanges claiming never to store your bitcoins on their servers for security purposes - while that sounds great, how is it possible? Surely the exchange would have no idea how many bitcoins you actually had at any one time?
Bitcoins are not stored anywhere. Never. There's only a list of transactions.
It's all a matter of public addresses (the only thing required to receive coins and check balances) and private keys (the only thing needed to spend coins). And as others explained, most private keys are not stored on the servers.
The above is a very succinct, accurate description of the reality. There are no coins in reality -- only a public ledger of balances. These balances can only be transacted using private keys, and most exchanges keep the majority of their coins stored on an address which has a corresponding private key that is
kept offline.So there is an offline private key which controls (say) 90% of the coins, and an online private key which controls 10% of the coins. This way if the server is hacked, only 10% of the coins can be stolen.
However, let's keep in mind that
the server operator himself could still steal 100% of the coins. (You have to trust him.) Remember what happened with MyBitcoin.com ?
This is why I think that a higher solution is to store the coins in a
multi-sig voting pool on the blockchain, so that you don't have to trust individual servers.