Removing non-stationarity just makes statistical structure of of your time series independent of absolute time-steps. It will typically reduce the auto-correlation but will not remove them. In some cases, it might happen that the time series consists of a deterministic seasonal component with some white-noise superimposed on it. In this case, removing non-stationarity will remove auto-correlations. But this is a special case.
A time series $X_t$ is stationary if the joint probability distribution of ${x_{t_1},x_{t_2},x_{t_3},x_{t_4},...,x_{t_n}}$ and ${x_{t_1+c},x_{t_2+c},x_{t_3+c},x_{t_4+c},...,x_{t_n+c}}$ is same for all $n$ and $c$. Intuitively, it means that if that the joint distribution depends upon the relative position of your time-steps, not the absolute position.
With some work, this definition translates to some important facts:
(1) Probability distribution of $X_t$ is same for all $t$.
(2) Expected value of $X_t$, $E(X_t)$, is independent of $t$: the mean does not change with time.
(3) In fact, the variance and all the higher moments do not change with time.
(4) The correlation between $X_{t_1}$ and $X_{t_2}$ is a function of $t_1-t_2$: it does not depend upon on $t_1$ and $t_2$, only on their relative positions.
Typically, a time series such as rainfall have seasonal fluctuations. Rainfall would be higher in Monsoon months than in other months. It means that the probability distribution of rainfall time series is changing with time (because the mean is changing with time). This is the reason behind removing the trends and seasonal components before using the classical time-series methods based on the assumption of stationarity.
Yes, autocorrelation implies temporal dependence. But both stationary and non-stationary time series have temporal dependence. The nature of dependence is different for stationary and non-stationary time series. In stationary time series, the autocorrelation depends on relative position of the time-steps only. In non-stationary time series, it can also depend upon the absolute value of time-steps.
Edit: (Based on a comment by Dilip Sarwate) The stationarity definition given above defines strict sense stationarity. However, for time-series analysis, what we typically requires is something called weak sense stationarity. A time series is stationary in weak sense if the expected value does not change with time and autocorrelation at time-steps $t_1$ and $t_2$ is a function of $t_1-t_2$ only. Weak sense stationarity does not satisfy the fact (1) mentioned above.