You do have to pedal fast enough and with enough power to make a difference. It truly is exercise to ride this way. I am out of shape but did learn to pedal about 250 cadence or times per minute. I doubt I can do much more than 180 pedal strokes per minute anymore. This gets me up to about 27 or 28 mph which is 3 or 4 mph faster than my motor wants to go on flat ground.
A bicycle with a 26-inch wheel, a 48-tooth chainring, and a cassette with gears ranging from 11 to 34 teeth has a lowest gear of 26 × 48 / 34 = 36.7 gear inches and a highest gear of 26 × 48 / 11 = 113 gear inches. Gear inches is the inch total one revolution of the crank and rear cog move the bicycle, so each pedal stroke can, in this example move you 113 inches. A smarter person than me can tell you from this info how fast to pedal for different speeds.
This part of the figuring is wheel diameter times chainring divided by rear cog, 26 X 60 = 1560 / 11 = 141.82" You can see from this that If you want to pedal slower or go faster get with Andrew and get a bigger set of chainrings. You could probably do a 60 / 48 / 38 or some such triple set up. You don't want more than 10 or 12 teeth between chainrings or shifting gets worse. I do shift a lot as I ride because I am looking for a comfortable cadence to help my motor. Every time I stop I change from high gear of about 113 gear inch to 36 X 18 or so which starts me up easily.
Sorry I am so long winded but I must give a warning also. Knees are a bike riders friend but if you have knee problems they can stop you short. Lance Armstrong and most other great modern cyclists could pedal hour after hour at 120 cadence. That is each second the pedal on the right goes around 2 times, and same with the left pedal. For he and most trained cyclists this allows the leg to work aerobically and the heart and lung supports the work. They are using gearing to lighten the weight they are moving with each pedal stroke.
Some cyclists insist on pedaling slower and powerfully in a larger gear. This tends to wear the knees out and causes problems, including fatigue and lactic acid build up. There are few Lance Armstrong's but he was a quick study about what would help him win and this is a key that will translate to anybody and making their riding less stressful on knee joints and less tiring.