Are you paraphrasing, or do you remember any sources that specifically refer to "constellations"? Doing a text search (control-F, or command-F if you're using a Mac) of "The Call of Cthulhu" online shows no instances of the word "constellation", but there are several parts that predicted Cthulhu would come back "when the stars were right". Here's the section that gives the most detail, discussing what had been revealed by a Cthulhu cultist named Castro:
Old Castro remembered bits of hideous legend that paled the speculations of theosophists and made man and the world seem recent and transient indeed. There had been aeons when other Things ruled on the earth, and They had had great cities. Remains of Them, he said the deathless Chinamen had told him, were still to be found as Cyclopean stones on islands in the Pacific. They all died vast epochs of time before men came, but there were arts which could revive Them when the stars had come round again to the right positions in the cycle of eternity. They had, indeed, come themselves from the stars, and brought Their images with Them.
These Great Old Ones, Castro continued, were not composed altogether of flesh and blood. They had shape—for did not this star-fashioned image prove it?—but that shape was not made of matter. When the stars were right, They could plunge from world to world through the sky; but when the stars were wrong, They could not live. But although They no longer lived, They would never really die. They all lay in stone houses in Their great city of R’lyeh, preserved by the spells of mighty Cthulhu for a glorious resurrection when the stars and the earth might once more be ready for Them. But at that time some force from outside must serve to liberate Their bodies. The spells that preserved Them intact likewise prevented Them from making an initial move, and They could only lie awake in the dark and think whilst uncounted millions of years rolled by. They knew all that was occurring in the universe, but Their mode of speech was transmitted thought. Even now They talked in Their tombs. When, after infinities of chaos, the first men came, the Great Old Ones spoke to the sensitive among them by moulding their dreams; for only thus could Their language reach the fleshly minds of mammals.
Then, whispered Castro, those first men formed the cult around small idols which the Great Ones shewed them; idols brought in dim aeras from dark stars. That cult would never die till the stars came right again, and the secret priests would take great Cthulhu from His tomb to revive His subjects and resume His rule of earth. The time would be easy to know, for then mankind would have become as the Great Old Ones; free and wild and beyond good and evil, with laws and morals thrown aside and all men shouting and killing and revelling in joy. Then the liberated Old Ones would teach them new ways to shout and kill and revel and enjoy themselves, and all the earth would flame with a holocaust of ecstasy and freedom. Meanwhile the cult, by appropriate rites, must keep alive the memory of those ancient ways and shadow forth the prophecy of their return.
In the elder time chosen men had talked with the entombed Old Ones in dreams, but then something had happened. The great stone city R’lyeh, with its monoliths and sepulchres, had sunk beneath the waves; and the deep waters, full of the one primal mystery through which not even thought can pass, had cut off the spectral intercourse. But memory never died, and high-priests said that the city would rise again when the stars were right.
Chances are Lovecraft just intended this to be suggestive of eerie cosmic horror rather than having a specific idea of what it meant for the stars to be "right", especially since this was just the description of people belonging to an ancient cult who would not have been very sophisticated about astronomy. But if the description was at least approximately correct, I imagine it could fall into any one of these categories:
How the stars look as seen from Earth. In this case, it could perhaps refer to the 26,000 year precession of the equinoxes which shifts which constellation the Sun is in at the equinox (it's always in one of the constellations of the Zodiac, so this is where the notion of the Age of Aquarius comes from) along with other changes like which star is closest to the North and South celestial poles (the "North Star" of Polaris will no longer be the one closest to the North celestial pole a few thousand years from now).
The spatial arrangement of the stars relative to each other, due to the stars' own proper motion.
Other intrinsic features of stars that change over long periods, like whether there have been any novas in a given volume of space recently, or some fictional change like a large chunk of one of the pieces of weird matter from "The Colour Out of Space" falling into a star and causing it to emit some mysterious radiation which our instruments are not yet capable of detecting. Another fictional possibility that occurs to me: several beings in Lovecraft's stories have wings which they are said to use to fly through the "ether" in space, probably inspired by real-world ether theories that posited an invisible substance filling space like an atmosphere. For example, the historical records of the Great Old Ones in "At the Mountains of Madness" revealed "They seemed able to traverse the interstellar ether on their vast membranous wings", and of the Mi-Go in "The Whisperer in Darkness" it was said "The things come from another planet, being able to live in interstellar space and fly through it on clumsy, powerful wings which have a way of resisting the ether." Cthulhu, too, was depicted as having "long, narrow wings" in a sculpture mentioned in "The Call of Cthulhu," though the wings weren't mentioned when the characters actually saw Cthulhu. Still, this suggests Cthulhu, too, may have flown using the ether--and so we could imagine that only certain regions of space have ether currents sufficiently strong to allow this, and our solar system only occasionally passes through one, perhaps due to the rotation of the galaxy as @Scott suggested in his answer (one could also imagine Cthulhu uses ether currents for energy like a plant getting energy from the Sun, and so must go into hibernation when they are not present).
Some evidence favoring 2 or 3 over 1 might be the line "When the stars were right, They could plunge from world to world through the sky; but when the stars were wrong, They could not live", which seems to suggest it's independent of Earth's perspective, though I suppose it's possible the Great Old Ones might be active in other regions while being dormant on Earth. And it's possible Lovecraft did intend to refer to the precession of the equinoxes (which often crops up as important to long-term historical cycles in occult literature, sometimes along with additional pseudoscientific claims of other Earth shifts as in Theosophy which Lovecraft had some passing familiarity with, in fact 'The Call of Cthulhu' contains the line 'Theosophists have guessed at the awesome grandeur of the cosmic cycle wherein our world and human race form transient incidents') and just didn't think about this issue that it doesn't make sense for an Earth-centered phenomenon like precession to have an effect on beings far from Earth.