Q:

What is covariance in plain language?

What is covariance in plain language and how is it linked to the terms dependence, correlation and variance-covariance structure with respect to repeated-measures designs?

A:

Covariance is a measure of how changes in one variable are associated with changes in a second variable. Specifically, covariance measures the degree to which two variables are linearly associated. However, it is also often used informally as a general measure of how monotonically related two variables are. There are many useful intuitive explanations of covariance here. 
Regarding how covariance is related to each of the terms you mentioned: 
(1) Correlation is a scaled version of covariance that takes on values in $[-1,1]$ with a correlation of $\pm 1$ indicating perfect linear association and $0$ indicating no linear relationship. This scaling makes correlation invariant to changes in scale of the original variables, (which Akavall points out and gives an example of, +1). The scaling constant is the product of the standard deviations of the two variables.  
(2) If two variables are independent, their covariance is $0$. But, having a covariance of $0$ does not imply the variables are independent. This figure (from Wikipedia) 
$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ 
shows several example plots of data that are not independent, but their covariances are $0$. One important special case is that if two variables are jointly normally distributed, then they are independent if and only if they are uncorrelated. Another special case is that pairs of bernoulli variables are uncorrelated if and only if they are independent (thanks @cardinal).
(3) The variance/covariance structure (often called simply the covariance structure) in repeated measures designs refers to the structure used to model the fact that repeated measurements on individuals are potentially correlated (and therefore are dependent) - this is done by modeling the entries in the covariance matrix of the repeated measurements. One example is the exchangeable correlation structure with constant variance which specifies that each repeated measurement has the same variance, and all pairs of measurements are equally correlated. A better choice may be to specify a covariance structure that requires two measurements taken farther apart in time to be less correlated (e.g. an autoregressive model). Note that the term covariance structure arises more generally in many kinds of multivariate analyses where observations are allowed to be correlated. 

A:

Macro's answer is excellent, but I want to add more to a point of how covariance is related to correlation. Covariance doesn't really tell you about the strength of the relationship between the two variables, while correlation does. For example:
x = [1, 2, 3]
y = [4, 6, 10]

cov(x,y) = 2 #I am using population covariance here

Now let's change the scale, and multiply both x and y by 10
x = [10, 20, 30]
y = [40, 60, 100]

cov(x, y) = 200

Changing the scale should not increase the strength of the relationship, so we can adjust by dividing the covariances by standard deviations of x and y, which is exactly the definition of correlation coefficient.
In both above cases correlation coefficient between x and y is 0.98198.

