I'm struggling to understand the value added by machines guessing at inputs to create a hash below a target value in order to produce a proof of work. I understand the proof of work is somehow supposed to inspire trust in the distributed record of transactions. How? Why should someone winning a lottery cause me to have trust in a blockchain?
Forget PoW for a second: lets instead imagine that you have a box, and you've placed a lock on it, in order to secure it's contents.
Now, if someone asks you how secure the contents are, then the size and type of lock is fairly important. Tying the box closed with a bit of string isn't very good security, at least compared to a heavy-duty padlock. For an attacker to get into the box and alter it's contents, they will need to work much harder to get past the padlock, compared to the string. We can use the word 'work' here in the thermodynamic sense: energy being used to perform an action. In order to break into the box, there is a minimum amount of work we would expect the assailant to have done. The minimum amount of work to break the padlock is obviously higher than the string, so we consider the padlock more secure.
Keep that point in mind: breaking into a more secure box requires more work. You cannot fake the work, you either have the resources to cut the lock, or not.
So lets go back to Bitcoin mining: when a miner is hashing to find a valid PoW, they are doing work by expending energy as computational cycles. The PoW function is devised such that we can expect a certain amount of work to be done (on average), in order for the miner to find a valid block. You can think of this PoW as the 'lock' that has been put on the block: in order for an attacker to alter the history of transactions, they will have to perform (on average) this same amount of work (spending energy, a real resource) in order to find a new, valid PoW and replace the block ('breaking the lock', as in our example from above).
Thus, the history of transactions is secured by miners spending energy to create the PoW that is required for a block to be valid. More energy spent mining creates a 'more secure lock', since a malicious miner would be expected to spend an equal amount of energy in order to break it. Miners are incentivized to continue building upon old blocks, thus piling one lock on top of another lock, on top of another lock... and it is this mechanism which allows the history of Bitcoin transactions to be considered secure.
It is because of the nature of the hashing algorithms and one-way functions in general. The amount of work to get an input that hashes below a certain value is directly related to how low that value is.
This is because there is no known way to reverse calculate the input of SHA256 that will result in a valid hash. The work is basically the number of guesses, on average, that it will take to get a valid hash at a given difficulty. While it is true that it is random chance to get a valid hash, the probability decreases with a lower value, so more work must be done (on average). It's important to think of it in terms of probabilities and average number of attempts required.
It inspires trust because in order to reverse the transactions, one must redo the work (or execute the same number of guesses - on average) in order for replacement blocks to be accepted in place of blocks in the existing chain. This is called a 51% attack.
It's not "a" lottery. Bitcoin transactions are considered reliable only after half a dozen or so blocks. Suppose someone wins the sixth lottery (lottery6). This results in block6, and it was built off of block5, which resulted from someone winning lottery5, and so on. Suppose you have a transaction in block1 where someone sent you some Bitcoin. If someone wanted to go back to back and insert a transaction into the blockchain where those Bitcoin instead go to someone else, they would have to go back to block0 and make an alternative block1b from that block with the new transaction. Block1b would then be in a shorter blockchain than the one where you received the Bitcoin. For that alternative transaction to be considered authoritative, at least five more blocks would have to be mined in that blockchain (five to tie the current blockchain and six to beat it), and all before any more blocks are added to the original blockchain. Not only would that take a tremendous amount of work, but miners would generally not have an incentive to work on that blockchain; if someone were to win the lottery and get block2b in the new blockchain, their mining reward wouldn't be secure until four more blocks are mined on that blockchain.
So a single person winning a lottery doesn't mean a transaction is secured, especially right after the block is found and hasn't propagated to all the nodes. But once a transaction is several blocks back in the blockchain, anyone who wants to nullify that transaction would have to basically either win lottery after lottery, or somehow get a majority of miners to participate in a massive conspiracy.