Your understanding is nearly correct regarding SHA-256 PoW.
Let's break it down. SHA-256 is a cryptographic hashing algorithm (that happens to be used as a PoW mechanism in some crypto currencies). CryptoNight is also a cryptographic hashing algorithm, although it's specifically used as a PoW mechanism (I don't know of it being used for anything else). They are both hashing algorithms though, they just internally work differently and have different properties. They both take input data and create a unique one way hash of that data.
The PoW mechanism is ultimately the same (which ever hashing algorithm you use). You take a block template, add a nonce (some random number), then hash. The output hash is a number. If that number is smaller than the current network difficulty target, you submit that block data (which has your nonce in it) to the network. If not, you increment the nonce (to simply change your input data) then repeat.
Verification of PoW is taken care of by the nodes receiving the submitted block data. Nodes hash (using the same hashing algorithm) the block data and if the resulting hash is smaller than current difficulty target, PoW is verified. Of course, to be added as the next top-block (and therefore get a reward) it also has to be first-seen (amongst other things).
It's better not to think about generating a certain amount of zero's, but rather finding a number (a hash) that's smaller than the current network difficulty target.
Technically speaking, with Monero, you are looking for a hash value that is greater than the current block difficulty. Imagine the maximum possible difficulty is 100 and the current block difficulty is 30. This means you are looking for a hash greater than 30 and less than or equal to the max possible value of 100 (so a possible range spanning 70, i.e. you have a 7 in 10 chance of finding a valid hash). If the network difficulty increases so the current block difficulty is 80, your range is smaller (20), thus harder to find a number in that range (i.e. a 1 in 5 chance). Note that the actual maximum hash value is 2^256-1, because our hashes are 256-bit numbers.