Susan Ratcliffe, Oxford Treasury of Sayings and Quotations, fourth edition (2011) reports that the saying is "modern":
The best time to plant a tree was twenty years ago. The second best is now. [Meaning:] even if you regret not having planted a tree, it is still worth doing so; modern saying
The precise number of years specified in various recitations of the saying as the best time to plant a tree generally ranges from 20 years ago (as in the Oxford Treasury version) to 25 years ago (as in Personal Finances: The Golden Rules for Making the Most of Your Money [1994]) to 30 years ago (as in the 1967 version from the Cleveland [Ohio] Plain Dealer cited in alphabet's answer). One outlier from 1995 (in a periodical called Strides), however, pegs the best time at five years ago, the second best as now, and the worst at "three years from now." Another source (McHenry's Quips, Quotes and Other Notes [1999]) argues for ten years ago. Yet another (Urban Forestry [1991]) pushes the ideal planting time back to fifty years ago.
Although Google Books and Hathi Trust search doesn't turn up any matches older than the 1967 instance in the Plain Dealer, they do produce several matches from the period 1968–1973.
From George Bagby, "Our Ruined Rivers," in Georgia Game and Fish (November 1968) [combined snippets]:
Many Georgians now recognize that steps must be taken and taken soon and fortunately there are things happening. It has been said that the best time to plant a tree was thirty years ago, the second best time is today. The same is true for conservation. The nest time to conserve the habitat necessary for our wildlife would have been fifty or a hundred years ago. The second best time is now.
This article from Georgia Game and Fish was subsequently reprinted in full in the Congressional Record of November 25, 1969).
From "If You're Going To, Better Get On with It," in Wisconsin Conservation Bulletin (March–April 1971):
The best time to plant a tree was 30 years ago. The next best time is now. (Said many times by many persons—original source unknown.)
This comment also appears verbatim in Timber Producers Association of Michigan and Wisconsin, The Timber Producer, volumes 27–28 (1971–1972).
And from Wisconsin Insect Survey Bulletin*, volumes 13–18 (1968–1973):
The best time to plant tree was thirty years ago. The next best time is now. Anon ---
We thus have early instances of the expression notes in Ohio (in 1967, cited in alphabet's answer), in Georgia (in 1968), in Wisconsin (1n 1971), Michigan/Wisconsin (in 1971–1972), and again in Wisconsin (in 1968–1973). None of these early instances suggests that the quote originated in China or that it is an old saying.
As it happens, there is a Chinese proverb about planting trees—but it is less aspirational than the one that the poster asks about here. From Josh Rohsenow, ABC Dictionary of Chinese Proverbs (Yanyu) (2003):
If you plant a tree in the morning, it is unrealistic to expect to sit in the cool of its shade by the evening. (fig[urative meaning:]) One should be realistic in one's expectations.