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 whatever they use now... I forget it's nameLyra2RE (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.