There was very recently a short note in the Pacific Daily News published on Guam and in the Marianas Variety published on Saipan that CO was changing or increasing the flights to and from Cairns.

So it probably wouldn't hurt to search for the GUM-CNS and CNS-GUM flights first, or consult a schedule, prior to doing the real booking.

Does CO even have an online schedule, other than through booking engine searches?