That is, for the set of predicted values $\{\hat{Y}_1, \hat{Y}_2, ...\}$ and the set of original values $\{Y_1, Y_2, ...\}$, the means of the sets are always equal.
The difference between the predicted values and the original values are the residuals
$$\hat{Y}_i = Y_i + r_i$$
So you can write
$$\begin{array}{} \frac{1}{n} \left(\hat{Y}_1+ \hat{Y}_2+ ...\right) &=& \frac{1}{n} \left(({Y}_1 + r_1)+( {Y}_2+r_2)+ ...\right) \\ &=&\frac{1}{n} \left({Y}_1+ {Y}_2+ ...\right)+\frac{1}{n} \left(r_1+ r_2+ ...\right) &=&\frac{1}{n} \left({Y}_1+ {Y}_2+ ...\right) \end{array}$$
and the last equality is true if the method has by design the following property $\left(r_1+ r_2+ ...\right) =0$ and that is the case for OLS. But note that this is only the case when the regression has an intercept term (as Christoph Hanck's answer explains). The residual term is perpendicular to the regressors. If the intercept is one of the regressors (or more generally as jld mentioned in the comments, if it's in the column space of the regressors) then the perpendicularity has as consequence that $\left(r_1,r_2,...\right) \cdot \left(1,1,...\right) = \left(r_1+ r_2+ ...\right) =0$
In simple words you could say that the $\hat{Y}$ are placed equaly in between the $Y$, as much above as below, and that is why they have the same mean.