A regression is a statistical relation between an output variable and one or many input variables. The most common kind of regression is a linear regression, where one finds a linear relationship between a set of input variables and an output variable.
Not all regressions have to be linear. There are various kinds of logistic regressions, for instance, that work better than linear regressions on estimating probabilities (since linear regressions are unbounded and can break through the 0 to 1 range).