The idea behind PoW is that it is easy to compute a hash of a transaction, but hard to find a transaction where the hash has certain properties. IOTA uses Curl hash function for this, and the Proof of Work requires that the hash ends with a certain number of zero trits (or when written as trytes, a certain number of nines). This number of zeros (also known as the Minimum Weight Magnitude, MWM) is currently 14 on mainnet and 9 on testnet.
This is easy to verify (compute one hash), but to find one, the entity that performs PoW has to guess nonces until it finds one that satisfies this condition (so it has to compute in average
3^14/2 (about 2.3 million) hashes).
Whenever a transaction is sent to a node (being it from a light wallet or from another node), the receiving node has to calculate the transaction hash (used for bookkeeping and later retrieving the transaction again). After calculating the hash, the node counts the number of zero trits at the end. In case there are less than MWM zeros at the end, the transaction is rejected and not stored on the node.
In case the transaction was received from a neighbor node, the "invalid transaction received" counter of that neighbor is increased, so a misbehaving or malicious node (which sends lots of invalid transactions) will appear when the node operator reviews his neighbor statistics.