Mitigating the negative impacts of declining worldwide forest cover remains a significant socio-ecological challenge, due to the dominant role of human decision-making. Here we use a Markov chain model of land-use dynamics to examine the impact of governance on forest cover in a region. Each land parcel can be either forested or barren (deforested), and landowners decide whether to deforest their parcel according to perceived value (utility). We focus on three governance strategies: yearly incentive for conservation, one-time penalty for deforestation and one-time incentive for reforestation. The incentive and penalty are incorporated into the expected utility of forested land, which decreases the net gain of deforestation. By analyzing the equilibrium and stability of the landscape dynamics, we observe four possible outcomes: a stationary-forested landscape, a stationary-deforested landscape, an unstable landscape fluctuating near the equilibrium, and a cyclic-forested landscape induced by synchronized deforestation. We find that the two incentive-based strategies often result in highly fluctuating forest cover over decadal time scales or longer, and in a few cases, reforestation incentives actually decrease the average forest cover. In contrast, a penalty for deforestation results in the stable persistence of forest cover (generally >30%). The idea that larger conservation incentives will always yield higher and more stable forest cover is not supported in our findings. The decision to deforest is influenced by more than a simple, "rational" cost-benefit analysis: social learning and myopic, stochastic decision-making also have important effects. We conclude that design of incentive programs may need to account for potential counter-productive long-term effects due to behavioural feedbacks.