"Optimal" cadence varies with what you're trying to optimze, so your question doesn't have a simple answer.
Freely-chosen Cadence vs. a Targeted Cadence
A recent review by Hansen et al. summarizes what is currently known about factors affecting choice of cadence. In particular, they conclude "[d]uring high-intensity cycling, close to the maximal aerobic power output, cyclists choose an energetically economical cadence that is also favorable for performance. In contrast, the choice of a relatively high cadence during cycling at low-to-moderate intensity is uneconomical and could compromise performance during prolonged cycling." The first sentence means that experienced cyclists freely choose the cadence that produces good performances and they don't need to have someone dictate what that cadence is. The last sentence means that having an inappropriate cadence forced on you can be detrimental to performance.
Cadence and Power
The relatively recent proliferation of on-bike power meters that record both power and cadence has helped provide additional data that bears on the issue. By definition, a cyclist's power output = cadence * crank torque * a conversion constant (the conversion constant depends on the units you use for measuring power, cadence, and torque; if you measure power in watts, cadence in radians per second, and crank torque in Newton meters, the conversion constant is 1). If you are racing at high power, or riding leisurely at low power along a bike path with your children, or on a spirited ride with friends, you will certainly choose different power levels; what has become clear from the data is that riders, even very experienced ones, choose different combinations of cadence and crank torque to match higher or lower levels of power. They do not always choose a fixed cadence and change gears in order to keep in robotic lockstep with that number.
Cadence and the Type of Ride
But even if we exclude leisurely riding and focus only on racing (at high power), cadence and crank torque vary according to the type of race. Here are cadence-crank torque plots for the same (domestic pro) rider in three different types of races: a road race, a criterium race, and a time trial. Torque is measured in Newton-meters, while cadence is measured in rpm. The thin red dotted lines show the combinations of cadence and torque that produce 300, 500, and 700 watts. As you may be able to see, the three different types of races call for different combinations of cadence and crank torque. The time trial shown here was done at a relatively steady power level but the road race and criterium race were much more variable. For those races, the rider attained higher power by increasing both cadence and crank torque. This is a quite common pattern for road racing, and it helps to explain why observers often remark that racers pedal at high cadence: the racers are also pedaling at high power and high crank torque but the only visible clue is the high cadence. This, then, is the basis for the sentences quoted from Hansen et al. above: the cadence used to produce high power appears to be neither economical nor performance-enhancing at low power. Just because you see a Tour de France rider pedal at X rpm doesn't mean you should pedal at X rpm (unless you also produce Tour de France levels of power). Likewise, just because you see that a Tour de France rider spends little of his time at Y rpm doesn't mean you should avoid pedaling at Y rpm. Your needs, abilities, and goals will differ.
Cadence and Terrain
Your question also asked whether cadence varies with terrain. Here is a plot of cadence and torque for a rider who was doing a set of hill intervals. The upper left panel shows his cadence and torque over the entire ride. The upper right panel shows the elevation profile for his ride; as can be seen, the ride was slightly rolling from his house out to a hill which he climbed and descended four times, then he returned home over the rolling road. That upper right panel marks the climbing portion of his ride in red. The bottom two panels show his cadence and torque for the corresponding black and red portions of the ride. As before, the thin dotted lines (this time, in blue) show "isopower contours." Clearly, he used different combinations of cadence and torque on the climbing sections than on the descending and rolling sections.
To emphasize this point, here is a plot that shows cadence vs. estimated road gradient for ProTour rider Gustav Larsson during Stage 3 of the 2009 Tour of California. As you can see, even if we exclude periods of coasting, his cadence varied from around 20 rpm up to around 120 rpm, and as the road gradient became steeper, his cadence decreased.
Cadence and Crank Torque
Do you wonder about the relationship between cadence and crank torque? Here is a plot showing another rider in a "pure" hill climb. The upper left panel shows the relationship between cadence and power; the upper right shows the relationship between crank torque and power; and the bottom two panels show the relationship between cadence and crank torque, one with and one without isopower contours. The bottom panels make clearer that there is often an inverse relationship between cadence and crank torque, but the upper panels show that in this instance crank torque was a larger determinant of power output than cadence.
Cadence and Knee Strain
Some riders claim that slow cadences (below, say, 60 rpm) can injure knees. However, slow cadence cannot by itself injure knees; as you sit at your desk reading these words, your “cadence” is almost surely close to zero but the force on your knees is also low. Riders who make these claims are conflating low cadence with high force. From the plots provided it should be clear that one of the simplest ways to expose the knees to lower force is simply to ride at lower power. Riding at 60 rpm at low power can be done with low pedal force; riding at 90 rpm at high power must be done with high pedal force. So level of power output (also known as “workload”) is a key to understanding joint strain. In the mid-1980s, M. Ericson published a series of studies examining forces on the hip, knee, ankle, foot, and the leg muscles during cycling including this one. Importantly, he concluded, “[o]f the four parameters studied (workload, pedalling rate, saddle height, pedal foot position) workload was the most important adjustment factor for change of joint load and muscular activity. An increased pedalling rate increased the muscular activity in most of the muscles investigated, generally without changing the joint load. Increased saddle height decreased the maximum flexing knee load moment, but did not significantly change the flexing hip or dorsiflexing ankle load moment. Muscular activity in most of the muscles investigated was not generally changed by different saddle heights.”
Cadence and trainers
Some riders will use their indoor trainers and observe that their "preferred"
cadence (perhaps for a particular level of power or heart rate) is X rpm, and then try to ride at that rpm outdoors. As we have seen above, freely-chosen cadence varies with terrain, power, and the way that resistance scales with speed. Of importance here is that trainers also vary in the way that resistance scales with speed. Below you can see a plot for the same rider on two different types of trainers but using the same gear ratio on both: a trainer with a fluid resistance unit, and on rollers. Each dot shows the cadence and crank torque at one second intervals. As you can see, these two types of trainers have very different resistance curves, with the rollers being much "flatter" with increasing rpm. In order to attain the same power, the rider appears to choose higher cadence (and lower crank torque). In order to attain the same level of power (say, 175 watts) the rider's freely chosen cadence varies with the type of resistance. "Transferring" indoor trainer cadence to an outdoor ride ignores both that outdoor rides vary, but also that trainers vary.
"...but..but the hour record is set at high cadence!"
Yes, most of the UCI hour records over the last 50 years have been set with cadences from about 100 rpm to 107 rpm (with the notable exception of Obree, who set his records at 93 and 95 rpm). However, the hour record is set with a fixed-gear bicycle on a track and, more importantly, all of the records have been set at high power and high crank torque. Below you can see the cadence and crank torque for many of the recent hour records based on data from Bassett et al.; the plot shows that for recent records set at sea level, average power ranged from around 370 to 460 watts and crank torque ranged from 36 to 43 Nm. One wouldn't tell a novice rider to pedal at a constant crank torque of 40 Nm yet many advise novices to ride at close to 100 rpm. Using the cadence of world record setting events achieved on a fixed gear on a velodrome track as a guide for more general riding makes about as much sense as using the crank torque of the same world record setting events achieved on a fixed gear on a velodrome track as a guide for more general riding.
In the image below, I plot cadence on one axis and crank torque on the other. The two dotted lines show two different power levels, in this case 200 and 300 watts. Suppose a rider was somewhere along the 200 watt line. There are an infinite number of combinations of cadence and torque that will produce 200 watts, but suppose they were at the red dot. Suppose they wanted to increase power from 200 to 300 watts. There are also an infinite number of combinations of cadence and torque that will produce 300 watts. I've drawn just 4 "expansion paths" that the rider could use to get to 300 watts: one is mostly vertical (that is, y cadence about the same and increased crank torque), one is mostly horizontal (that is, crank torque about the same and increased cadence), one that goes off diagonally (where both cadence and crank torque increase), and one that extends upward and to the left, where cadence actually drops but crank torque increases even more. We've seen examples of all of these expansion paths in the plots above.
The terrain, the acceleration, the wind, and (critically) where the red dot is on the 200 watt line (that is, the rider's cadence and torque) all influence the power expansion path that is actually chosen. Not shown but in other cases, the cadence can increase while the crank torque decreases (for example, if the red dot happened to be at a point where cadence was already low and crank torque was low). Cadence and crank torque are jointly determined, depending on what the rider is facing, and what the rider wants to do. Admittedly, some riders may lean a little bit more toward modulating their power with cadence, others may lean a little bit more toward torque, but everyone is adjusting both, all the time.
The conclusion from all of this is that cadence varies both with the ride and with the rider. In that sense, asking about "optimal cadence" is, in isolation of the characteristics of the ride and rider, a red herring. Without the proper context, asking about optimal cadence is like asking about optimal power, or optimal crank torque.