There are several ways in which this apparent paradox can be resolved.
As a starting point, it is important to consider how heritability is defined and assessed (also see this earlier answer). As you point out, heritability estimates originate from comparisons between people who differ in their genetic similarity (e.g., monozygotic vs. dizygotic twins). The high heritability for IQ means that genetic similarities correspond to a high similarity in IQ. It's crucial to note, however, that heritability only describes the extent to which differences in the phenotype (in this case IQ) overlap with differences in the genotype in a given population. In other words, heritability describes how much of the variance in a trait statistically corresponds to genetic variance (see e.g., Griffith et al. 2000). Heritability does not describe the extent to which genes actually cause IQ differences, only the correspondence of genetic similarity and IQ similarity. In this vein, high heritability does not exclude the possibility of environmental influences on IQ:
For example, one reason for the rise in IQ may be better nutrition. If everybody in a society gains access to better nutrition to the same extent, this may increase IQ for all. Nevertheless, heritability does not necessarily change as the genetic differences between people still translate into IQ differences between people.
Environmental changes may actually increase heritability estimates. For example, consider a country in which people in one geographical region have access to good education (another potential reason for the Flynn effect), and people in another region don't. If missing opportunities for education depresses IQ points, the population's variation in IQ should be affected by this environmental difference. Once good education becomes available for everybody, genetic differences should matter more, leading to a higher heritability estimate.
A detailed model of how high heritability estimates and large environmental influences on IQ can coexist has been proposed by Dickens and Flynn (2001). In their analysis they focus on the possibility that environmental influences can be underestimated because genes and environment shape IQ interactively, in a way that is not captured by heritability estimates.
- They assume that small genetic advantages can translate into strongly favorable environments. For example, if a child is somewhat smarter than others, she will have a higher chance to end up in a better school, where she can thrive, and then go to a better college and so on (an individiual multiplier). Nevertheless, this environmental influence would be ascribed to genes, because of the way heritability is defined.
- There may also be a social multiplier effect caused by the social environment one lives in. If average IQ in the society is rising for some external reason, everybody should profit from this rise. For example, if more people go to college because this now offers lucrative jobs, this may set examples, encourage others to do the same, make college education itself more widely available, and thus create a social dynamic that leads to IQ gains for all.
Another possibility to resolve the paradox may be to investigate whether the Flynn-effect is actually due to genetic causes. Mingroni (2007) posits that higher social mobility has reduced inbreeding of people who live in high social isolation, which is detrimental to IQ. However, reviewing empirical evidence, Nisbett et al. (2012) conclude that this hypothesis seems implausible, for example, because the Flynn effect is also observed in societies which have been characterized by high social mobility for a long time.
In conclusion, even though there is no consensus on the exact reasons for the Flynn effect (Nisbett et al., 2012), there are several ways in which high heritability estimates for IQ and the large gains in IQ (due to environmental reasons) can be reconciled.
References
Dickens, W. T., & Flynn, J. R. (2001). Heritability estimates versus large environmental effects: the IQ paradox resolved. Psychological Review, 108, 346–369.
Griffiths, A. J., et al. (2000). An Introduction to Genetic Analysis (7th ed.). New York: W. H. Freeman. http://www.ncbi.nlm.nih.gov/books/NBK21766/
Mingroni, M. A. (2007). Resolving the IQ paradox: Heterosis as a cause of the Flynn effect and other trends. Psychological Review, 114, 806–829. doi:10.1037/0033-295X.114.3.806
Nisbett, R. E., Aronson, J., Blair, C., Dickens, W., Flynn, J., Halpern, D. F., & Turkheimer, E. (2012). Intelligence: New findings and theoretical developments. American Psychologist, 67, 130–159. doi:10.1037/a0026699