How balances are calculated? Is it the case that the blockchain has information on the balance associated with each public key-address, such that the client on my PC, say, will look at every public/private keys pair in wallet.dat, find all public keys in the blockchain for each of my private keys, sum up the balances for each, and show me the overall balance?
The Bitcoin-Qt/bitcoind client computes the balance as you describe, by summing up all the transactions for all the Bitcoin addresses in the wallet.dat.

The blockchain contains all transactions since the genesis block (block 0).  So the balances are simply all the unspent transaction outputs (UTXOs).

There are third party services which will monitor the blockchain to provide balance info for a specified address or addresses.  BTCBalance.net is one.