bitcoind uses stochastic approximation to select a subset of unspent outputs to spend.
(actual code : https://github.com/bitcoin/bitcoin/blob/master/src/wallet.cpp#L1043-L1185)

There is an old thread about it here: https://bitcointalk.org/index.php?topic=29207.0

Bitcoin wiki (https://en.bitcoin.it/wiki/Main_Page) is probably the best source of technical information about bitcoin protocol.
You can find etotheipi's diagrams there (e.g., https://en.bitcoin.it/w/images/en/7/70/Bitcoin_OpCheckSig_InDetail.png, https://en.bitcoin.it/w/images/en/9/9b/PubKeyToAddr.png).

There is a pull request that adds support for watch-only addresses to bitcoind : https://github.com/bitcoin/bitcoin/pull/2861. This PR allows to track transactions and balances without having to know and keep associated private keys in the wallet. Unfortunately, it is unclear when it will be merged.

It is also reported that people are using this in production (custom version of bitcoind).

I would also like to know more details on how to prove that some data exists without
creating unspendable outputs (I have no affiliations to proofofexistence service).

If a private key is lost, the bitcoins are gone forever.
Theoretically, it is possible to guess the private key, but it will take quite some time : http://bitcoin.stackexchange.com/questions/22/is-it-possible-to-brute-force-bitcoin-address-creation-in-order-to-steal-money/3205#3205

There is a service that uses bitcoin blockchain to prove that certain data exists at a certain moment of time http://www.proofofexistence.com . This is done by generating a  bitcoin transaction (unspendable) to two specially crafted addresses.

Intentional fork, as I understand, would mean an attack on bitcoin. The outcome of such event will depend on the amount of hashing power the attacker has.

At March 2013 a bug in Bitcoin 0.7 caused a hard fork of the chain that could not be automatically resolved (details : https://en.bitcoin.it/wiki/BIP_50).

This event didn't seem to affect bitcoin price and public image of bitcoin.

Now the situation is different. Bitcoin price has increased 30x times since March and now bitcoin is receiving more public attention than ever before.

I wonder what would have happened to bitcoin price if a hard fork had occurred now?