How exactly does the network know if the miner has put forth a valid proof of work? If all that the miner needs to do is find a hash with a certain number of leading 0's of the block's header, couldn't they just find a random hash with the required number of 0's that isn't necessarily the hash of the block header? How would the nodes know?

How exactly do the nodes decide if the proof of work is valid? What protocol is used for this?
When a miner authors a new block, the block contains a block header. The block header is used to put the new block in relation to previous blocks and gives a summary of the transactions. In detail, the block header contains:


a version byte
the block hash of the previous block
the Merkle root that commits to all transactions in the block
a timestamp
a field corresponding to the current difficulty
a nonce that provides some randomness.


This block header has only 80 bytes of data. When these 80 bytes are put through SHA-256d once, they result in a hash which we use as the unique identifier of the block, the "block hash". The block hash is used to announce the block to peers and in the next block to commit to this one. This same "block hash" interpreted as a number has to meet the difficulty requirement ("have a certain number of leading zeros").


  What you are saying is that the nodes have to do the work to find the valid hash all over again.


Not quite! Finding a block header for which the hash meets the difficulty requires a multitude of tries. Since it is impossible to predict which block header will succeed except by hashing and checking, the fact that a valid block has been found proves that a large number of tries have been expended (about 4,92×10²² in average currently). We call this concept proof-of-work. However, the validation of the work only requires to put the provided block header once through a hash function and then to compare the resulting hash with the difficulty which is trivial to do!
In fact, this is the first of a number of validity checks that other network participants do when they receive a new block candidate.