I don't completely agree with the given answers. Regression is a statistics problem that goes back to Galton in the 19th century. One of his early examples was to relate the height of fathers with the height of their grown sons. Galton coined the term regression: meaning regression toward the mean. What he observed was that if you look at tall fathers their sons will tend to also be taller than average but not as tall as their fathers. Also short fathers will have short sons but their sons will tend to be taller than their fathers. Hence regression toward the mean. The sons of fathers of a given height will tend to be closer to the mean value in height.
There is an apparent paradox called the regression fallacy. If we turn the problem around and look at the tall sons and ask what the height of their fathers is it? Father's height will turn out to be taller than average but not as tall as the son. There is really no contradiction here.
In statistics simple regression estimates the function f(x) that is the average of a variable Y given the Value of the variable X is x. The function f(x) is called the regression function and it is estimated based on a sample of paired values for X and Y.
Simple regression has been generalized to multiple regression where we consider the average Y given several predictors X$_1$, X$_2$, ..., X$_p$ and the regression function becomes f(x$_1$,x$_2$,...,x$_p$) the average of Y given X$_1$=x$_1$, X$_2$=x$_2$,...X$_p$=x$_p$. The model is fit using sets of p+1 dimensional vectors of observations
(y$_i$, x$_1$$_i$, x$_2$$_i$,...,x$_p$$_i$) for i=1,2, 3,...,n.
Linear regression refers to the case where f is linear in the coefficients of the predictor variables. The regression function for Y with p predictors X$_j$ j=1,2,..p is a linear function in the case where the joint probability distribution for Y and the X$_i$s is multivariate normal. Under the assumption that observed Ys differ from the regression function by a random normal error term with mean 0 and a constant variance and the X$_i$s are observed without error, the estimate of the parameters that minimize the squared deviations in the Y direction is "best" in the sense that it is the maximum likelihood estimator. These estimates are called least square estimates.
When the error terms are not normally distributed there are alternative (so-called robust) estimators that are better than least squares. When the Xs have error in their measurement the problem is called "error in variables regression" (aka Deming regression).
The regression function can also be nonlinear in the parameters and in that case we call the problem a nonlinear regression problem. This problem can be solved by the method of least squares. However in the linear case there is a nice closed form solution while in nonlinear regression numerical methods are usually needed to get the solution.
That is regression in a nutshell that is hopefully understandable.