Over-fitting Always Occurs?
Roughly speaking, over-fitting typically occurs when the ratio $\frac{\text{complexity of the model}}{\text{training set size}} $ is too high. Think of over-fitting as a situation where your model learn the training data by heart instead of learning the big pictures which prevent it from being able to generalized to the test data: this happens when the model is too complex with respect to the size of the training data, that is to say when the size of the training data is to small in comparison with the model complexity.

Examples: 


if your data is in two dimensions, you have 10000 points in the training set and the model is a line, you are likely to under-fit.
if your data is in two dimensions, you have 10 points in the training set and the model is 100-degree polynomial, you are likely to over-fit.




From a theoretical standpoint, the amount of data you need to properly train your model is a crucial yet far-to-be-answered question in machine learning. One such approach to answer this question is the VC dimension. Another is the bias-variance tradeoff.

From an empirical standpoint, people typically plot the training error and the test error on the same plot and make sure that they don't reduce the training error at the expense of the test error:



I would advise to watch Coursera' Machine Learning course, section "10: Advice for applying Machine Learning".