The focus of this paper is on trend estimation for a general state-space model $Y_t=μ_t+\varepsilon_t$, where the $d$th difference of the trend $\{μ_t\}$ is assumed to be i.i.d., and the error sequence $\{\varepsilon_t\}$ is assumed to be a mean zero stationary process. A fairly precise asymptotic expression of the mean square error is derived for the estimator obtained by penalizing the $d$th order differences. Optimal rate of convergence is obtained, and it is shown to be "asymptotically equivalent" to a nonparametric estimator of a fixed trend model of smoothness of order $d-0.5$. The results of this paper show that the optimal rate of convergence for the stochastic and nonstochastic cases are different. A criterion for selecting the penalty parameter and degree of difference $d$ is given, along with an application to the global temperature data, which shows that a longer term history has nonlinearities that are important to take into consideration.