Why do we need regularization for linear least squares given that a line is the simplest model possible? In linear least squares we are trying to fit a line to data. A line is the simplest model that can be fit to the data. How is it possible for a linear model to over-fit the data? In short why do we need regularization for fitting a line to a data?
I understand that regularization improves generalization performance ie over unseen datasets and reduces over-fitting to training data. But how would regularization reduce the over-fitting issue for a least complex model (i.e linear model)?
This question was posted on stackoverflow, was redirected here. Also asked on DataScience stackexchange, but I am yet to get any answers/comments on the same.

Another way of looking at it:  A linear model is not the simplest model that can be fitted to the data - a linear model with a constraint on the values of the weights is even more simple.  For example, if we constrain the number of non-zero weights, we have a model that is structurally less complex - it has fewer parameters.  As we increase the number of non-zero weights, we create a sequence of nested models of increasing complexity.  A model with three non-zero weights can do everything a model with two non-zero weights can do, and also a few things it can't, so it must be a more complex model in some sense.
We can do something similar with regularisation, but it is a bit more subtle.  We can create another sequence of models of increasing complexity by putting a constraint on the norm of the weight vector (limiting the magnitude of the weights rather than the number of non-zero weights).  We then have an optimisation problem of the form:
$\mathrm{min}_\vec{\theta} f(\vec{\theta}) \quad \mathrm{s.t.} \quad \|\vec{\theta}\|^2 < C$
where $\vec{\theta}$ is the vector of model parameters (weights) and $C$ is the hyper-parameter controlling the maximum allowed value of the norm of the parameter vector and $f(\cdot)$ is the loss function (e.g. sum of squares).  If we have a model with a particular value of $C$ and then increase $C$ a bit (to $C'$), then it can do anything it previously could, but it can also realize some additional mappings that it couldn't before.  So as we increase $C$, we create models that are potentially more and more complex.
How does this relate to regularisation?  One way of solving a constrained optimisation problem is to take the Lagrangian to turn it into an unconstrained optimisation problem, and in this case, the Lagrangian is:
$\Lambda(\vec{\theta},\lambda) = f(\vec{\theta}) + \lambda\|\vec{\theta}\|^2 - \lambda C.$
We can ignore the last term as it doesn't depend on the parameter vector, and what is left is a regularised loss function.
So we see that regularisation is a way of controlling the complexity of even  a linear model, by limiting the set of mappings it can implement.
If we think of one-dimensional regression tasks, it is difficult to find a lot of value in regularisation, but when we have models with lots of parameters, regularisation becomes more obviously useful.  Some of the attributes may be correlated with the target by random chance and have no predictive value.  Regularisation will help surprress those attributes, and result in a model with better generalsiation.
Modelling data generally involved fitting the complexity of the model (class) to the complexity of the data we have available, and regularisation provides a convenient way of doing that (it is a continuous hyper-parameter, so it is a bit less of a blunt instrument that e.g. feature selection).
Just to add, I've been a bit vague with terminology here.  Really is is nested sets of model/hypothesis classes rather than models, i.e. the set of models that could be realised within the constraint imposed by the value of the regularisation parameter (c.f. @Ben's answer).
