One option is to subsidize the trees as a future investment for the one planting. While this won't do much to get people to plan trees where cities are at, in more rural areas you can convince someone to plan trees that will be able to be harvested in 50+ years. The only catch is that the people who own land are likely old enough they won't see the returns themselves, but if you present this as a method for investing in your children's future it could get buy in. A contract could also include an early sell penalty to dissuade people form cutting too early. Something like "If you sell early, the government is owed 50% of the total sell value. This percentage reduces by 1 per year until it reaches 0% at 50 years. This is in addition to any taxes owed on the sell."
Also, just advertisement and information campaign aimed at getting people to plant trees in rural areas as an investment in their children's future would encourage more planting as well.
