What would be the smoothest transition for changing the PoW? Miners would need to be given a heads up to install new software but how would the switch over happen in practice? The block before the fork would be cryptonight and the block of the fork would be cuckoo cycle. I can only think of maybe having both the cryptonight code and cuckoo cycle code available in a miner and have code checking for what block it is so the miner knows what PoW to use. Later miners could just use a miner with only cuckoo cycle because cryptonight would no longer be needed after the fork period.
Yes, that's basically what would happen if Monero switched to any other PoW. A good example is Vertcoin's switch from Scrypt-N to Lyra2RE (and then to Lyra2REv2).
Essentially, the changeover works like every other hardfork in the network. A future block height would be picked as the changeover point, after which the proofs of work in the block would have to follow the new algorithm. Node software would have to maintain the capability of verifying the cryptonote PoW as well as the new one because new nodes would need to be able to verify the work in all the blocks before the fork. Mining software would be able to abandon all cryptonote related code, though.
Note that as of now, my understanding is that Cuckoo Cycle can't be pool mined, which means the transition would have to have miners ready to start solo mining at the right height. This would be an issue that would have to be thought out carefully.