My general sense from reading the intelligence literature is that I would not expect there to be much of a relationship between exercise and intelligence.
For example, if you read Neisser et al (1996) you can get an overview of the intelligence literature. From the review, you can get a sense of just how difficult it is to systematically increase intelligence, especially over longer periods of time. This includes many cognitive interventions. It seems likely to me that cognitive interventions are targeting intelligence more directly and thus if anything should be more effective than more indirect interventions, such as those targeting physical activity. That said, aerobic, strength, and general physical health is presumably related to energy levels and as studies suggest below may also be related to a range of cognitive and motivational processes relevant to effective life functioning.
Exercise for sedentary adults
Colcombe and Kramer (2003) performed a meta analysis on sedentary older adults and found that performance on cognitive tasks improved by .48 standard deviation relative to to .16 standard deviation improvement for control groups. The average improvement in cardiovascular only programs was 0.41 standard deviations, and the average improvement for combined programs (i.e., including resistance training) was .59 standard deviations. These studies used a variety of psychomotor and cognitive tasks. However, it did not appear that the studies used intelligence tests.
I take from these studies that exercise can have a beneficial effect on psychomotor functioning. However, I'm not persuaded yet that it exercise has a major effect on intelligence.
Exercise for children
For a review of research on exercise on children's cognitive function and academic achievement, see Tomporowski et al (2008). The authors conclude that "similar to adults, exercise facilitates children’s executive function (i.e., processes required to select, organize, and properly initiate goal-directed actions)."
They provide a narrative review of many existing studies on the topic.
- Tomporowski, P. D., Davis, C. L., Miller, P. H., & Naglieri, J. A. (2008). Exercise and children’s intelligence, cognition, and academic achievement. Educational Psychology Review, 20(2), 111-131. http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2748863/
- Neisser, U., Boodoo, G., Bouchard Jr, T. J., Boykin, A. W., Brody, N., Ceci, S. J., ... & Urbina, S. (1996). Intelligence: Knowns and unknowns. American psychologist, 51(2), 77.
- Colcombe, S., & Kramer, A. F. (2003). Fitness Effects on the Cognitive Function of Older Adults A Meta-Analytic Study. Psychological science, 14(2), 125-130.