The average recommendation is 25% water at least every month, however some tanks (usually the smaller ones) can require a 25% change every week. Every system is slightly different. The best way to tell is keep an eye on your water chemistry. When you see something rise above the norm. then it is time for a water change.
I always hesitate to suggest an answer to questions like this one (along with when can I add an octopus to a new tank). Thales often mentions getting your "saltwater thumb" well before keeping a ceph (or other sensative animal) because there is no pat answer. Discovering a routine that works (note the emphasis) is part of the thumb achievement (another part is noticing when something just is not right). Spending time to read not only the comments but why different aquarists use their methods is worth doing on a forum like Reef Central. Don't go there looking for a specific answer but to gain an understanding. Thales recently referenced a pod cast that tries to discuss our desire for a step wise recipe and the difficulty in creating one. A sticky with longer term tank owner's individual monthly routines and reasonings would be a nice addition to our tank talk thread.
Since there are many answers and many that work, how do you start? With a well cycled tank of course This alone will help you see when your routine is best working. For my own tanks, I find I must have an aggressive routine or I can get sloppy (evidenced when I have cephless octo tanks that don't get as much care on lazy Saturdays). I have too many tanks but can never seem to give one up so I have to commit what amounts to a full day every week to maintenance. All of my tanks are different volumes but my working routine is to change roughly 5 gallons (roughly because I use somewhat approximated markings on my holding tank but I use the same buckets to remove and refill each tank so the amount is consistent) of water every week in every tank.
My thinking behind this is that my smaller tanks contain hardier animals but pollute faster, lose more dissolved oxygen and don't have the filtration of the larger ones (one 8 gallon tank has nothing more than live rock for filtration, a 30 has a cannister and a 15 a small HOB). I would not keep something sensative to chemistry changes in the small tanks and still maintain the high percentage changes in one water change.
The larger tanks are better filtered but the monthly water change is not the cummulative ~35% (for a 65) but something less, however, the detritus build up is lowered by the more frequent maintenance and aeration improved over a larger monthly exchange. In the larger tanks smaller weekly percentage changes are less impactive on salinity, PH and temperature and I mix the new water in the sump rather than directly in the display.
Important to note, when I say water change, I do not imply simply swapping water as there is more to regular maintenance than just a water exchange. In addition to the mostly esthic window cleaning, I disturb and vacuum the bottom as well as vacuuming the rocks with the siphon hose, clean the filter sock and rinse the carbon. I try to target at least one larger tank each month (or two) for extra cleaning and will often double is water change. One of the ways you can monitor the effectiveness of your overall system and water change routine effectiveness is to check your nitrate levels. Unfortunately, low readings for a tank less than a year old are not particularly strong indicators that your routine is successful. Any detetable ammonia, nitrite or high nitrate are problem indicators any time after the primary cycle. Detectable presence of ammonia or nitrite (there will always be some, that is the way the cycle works but you should not be able to detect it with common hobbiest methods) spells trouble and a water change is the first thing needed to reduce stress. Determining why your cycle is failing and correcting the problem is an important second step.
IME, a 65-140 gallon ceph tank needs roughly 45 min - 1 hour a week of maintenance (in addition to daily freshwater - RO/DI but not salted - top off checks, feeding and removal of shells or other feeding debris).