Paying a transaction fee is optional. Miners can choose which transactions to process and prioritize those that pay higher fees. Fees are based on the storage size of the transaction generated, which in turn is dependent on the number of inputs used to create the transaction. Furthermore, priority is given to older unspent inputs.
In the blockchain, bitcoins are registered to bitcoin addresses. Creating a bitcoin address is nothing more than picking a random valid private key and computing the corresponding bitcoin address. This computation can be done in a split second. But the reverse (computing the private key of a given bitcoin address) is mathematically unfeasible and so users can tell others and make public a bitcoin address without compromising its corresponding private key. Moreover, the number of valid private keys is so vast that it is extremely unlikely someone will compute a key-pair that is already in use and has funds. The vast number of valid private keys makes it unfeasible that brute force could be used for that. To be able to spend the bitcoins, the owner must know the corresponding private key and digitally sign the transaction. The network verifies the signature using the public key.
If the private key is lost, the bitcoin network will not recognize any other evidence of ownership: the coins are then unusable, and effectively lost. For example, in 2013 one user claimed to have lost 7,500 bitcoins, worth $7.5 million at the time, when he accidentally discarded a hard drive containing his private key. A backup of his key(s) would have prevented this.