I have read that PoW is about finding a nonce such that:
hashOf(Block Data + Previous Block Data + Nonce) == A Hash With
Desired Leading Zeros
I suppose you mean
hashOf(Block Data + Previous Block Hash + Nonce).
And that once a miner has found this nonce, it can broadcast the nonce
to the network where each miner can validate that it is the correct
nonce by using the same function above.
No. Once a miner has found a nonce leading to a valid hash according to the current difficulty criteria, it should broadcast the block. Ethereum has a slightly more complicated and more memory oriented proof of work than what is usually used as an example, you can read more about it here but we can stick to the basic example.
But from my statement above I feel like if a Miner doesn't have a
standard mechanism for ordering and including transactions that
complies with at least 51% of the other miners then they will never be
able to mine a block.
Correct me if I'm wrong but it seems that you think of the consensus in PoW as miners generally agreeing on what transactions should be contained in a block. To do so they would indeed need to have a shared rule about which transactions to include, and in what order. However, they would also need to all have the same knowledge of pending transactions. That assumption cannot hold due to network delays / message drops / etc...
So it's not about having the right transactions, or any transaction for that matter, a block without transactions is perfectly valid (not including the coinbase tx) as you can see for Bitcoin or Ethereum.
What the consensus is really about is twofold :
- What is the mainchain (longest chain rule for Bitcoin, GHOST for Ethereum)
- Valid block content (hash and transactions)
What we call Proof of Work, is in fact known as Nakamoto Consensus (PoW + chain selection rule).
So when a miner aim to create a new block, it selects some transactions (or none) while maximizing the fees for their personal gain. Those transactions may only be known by this miner and the participants that created them, after all, each transaction includes a signature and the actions that it does can be checked against the current state. The miner then works out the proof of work by varying the block nonce and, if successful, broadcast it to the network.
Other participants will eventually receive that block and basically checks for the following :
- Hash is valid and matches difficulty criteria.
- All tx are valid (no one spends more than it owns / tx nonce are in increasing order if one account has several tx included in the block)
It doesn't matter that participants learn the existence of some previously unknown transactions when the block is received, transactions are signed and their validity can be checked. Plus, a transaction doesn't really "exist" before being included in a block, in the sense that it has no effect whatsoever prior to that inclusion.
If that new block extends the main chain, the state transition is applied and miners will use that block as parent block for their next block creation attempt. And you have a new consensual view of the current state of the blockchain that never required a network wide view of the pending transactions.
I hope that answers your question.