I'm getting confused about what I read about covariance. I know how to calculate covariance between two different variables, but not between two observations of the same variable. Imagine you have many observations of a variable $X$. What does this mean and how to calculate it?
$$ {\rm Cov}[x_i,x_j] $$
Or, which seems the same problem to me, in a simple linear regression when it is said that
$$ {\rm Cov}[\varepsilon_i,\varepsilon_j] = 0 $$
for $i \neq j$. How do you calculate this?
One useful way to rewrite the variance instead of square deviations from the mean is in terms of squared deviations from every other observation (via Wikipedia):
$${\rm Var}(X) = \frac{1}{n^2}\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{1}{2}(x_i - x_j)^2$$
You can imagine making a figure where $x_i$ are the rows and $x_j$ are the columns (where $i$ and $j$ both index the same observations in the same order), and the matrix is filled with the values of $\frac{1}{2}(x_i - x_j)^2$. You should not be able to shuffle the order of the observations to provide patterns in this matrix in the case of independent data.
When we are interested in auto-correlation of the series we need to define pairs of data in which to examine whether the variance within the pairs contributes a greater/lesser amount to the overall variance. That is pairs within this grouping are more similar than pairs outside of this groupings (for positive auto-correlation).
Some examples of this are:
For the suggested matrices above, if you have grouped data with positive auto-correlation and you placed the groups in order, the matrix would appear block like, with smaller values within the blocks are larger values between the blocks. For time series data if you order the observations by time, the matrix would appear diagonal, with smaller values on the diagonal and larger values off the diagonal for positive auto-correlation.
@AndyW has provided a nice answer. Let me throw out one small additional point relative to the "[w]hat does this mean" part of your question.
It does seem incomprehensible that there can be a covariance between two single points. What you need to bear in mind is that the two points you have are just realizations from two error distributions at two $X$ values. The assumption that ${\rm Cov}[\varepsilon_i,\varepsilon_j] = 0$ pertains to the error distributions of the data generating process, not actually to the realized data.
In theory, it is possible that the error distribution for March is correlated with the error distribution for February, but that all other pairings of error distributions would be perfectly uncorrelated. With just one data point each from February and March, this cannot be checked (it is also a very bizarre possibility). Instead, what we do, in effect, is test the residuals at lags. That is, we would check, e.g., the covariance of every data point with the point before it. Now you have two sets of data such that you can check the covariance.