How does proof of work inspire trust when the work is just guessing? 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 its 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 its 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 let's 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.