What question does ANOVA answer? I want to learn ANOVA. Before I start to learn how the algorithm works (what calculations have to be done) and why it works, I first would like to know what problem do we actually solve with ANOVA, or what answer do we try to answer. In other words: What is input and what is output of the algorithm?
I do understand what we use as an input. We have a set of numbers. Each number comes with values of one or more categorical variables (also known as "factors"). For example:
+------------+------------+-------+
|   factor 1 |   factor 2 | value |
+------------+------------+-------+
|     "A"    |     "a"    |  1.0  |
|     "A"    |     "a"    |  2.4  |
|     "A"    |     "b"    |  0.3  |
|     "A"    |     "b"    |  7.4  |
|     "B"    |     "a"    |  1.2  |
|     "B"    |     "a"    |  8.4  |
|     "B"    |     "b"    |  0.4  |
|     "B"    |     "b"    |  7.2  |
+------------+------------+-------+

Is it correct to say that ANOVA calculates p-value of null hypothesis that states that there is no effect of the factors on the mean of the values? In other words, we give the above given data to the algorithm and as a result we get the p-value of the null hypothesis?
If it is the case, what measure do we actually use to calculate the p-value. For example we can say that, given the null hypothesis M can be as high as the observed one (or even higher) just by chance in 1% of cases. What is M?
Don't we also investigate factors in ANOVA separately? Can ANOVA say that factor_1 has an effect but factor_2 not? Can ANOVA say, that for a given factor values corresponding to is value "A", "B" and "C" are statistically indistinguishable (have the same mean, for example) but value "D" has an effect?
 A: ANOVA stands for "Analysis of Variance".  Rather unsurprisingly, it analyses variance.
Let's be a little more explicit. Your observations will exhibit some variance. If you group your observations by your factor 1, the variance within the groups defined by factor 1 will be smaller than the overall variance. Factor 1 "explains variance".
However, this is not sufficient to conclude that factor 1 actually does have a relationship to your observations... because grouping by anything whatsoever will "explain" variance. The good thing is that we know how much variance will be explained under the null hypothesis that your factor does, in fact, have nothing to do with your observations. This amount of variance explained under the null is described by an $F$ distribution.
Thus, the strategy in ANOVA is to estimate overall variance and within-groups variance (using sums of squares) and taking ratios of these estimated variances. This ratio is the $F$ statistic. We then compare this $F$ statistic to the critical value of the $F$ distribution in a one-sided test, yielding your $p$ value. The number of factor levels goes into one parameter of the $F$ distribution (more factor levels will explain more variance under the null hypothesis), and the number of observations and the number of levels goes into the other. This earlier question may be helpful.
(Why a one-sided test? Because, as above, any grouping will explain some variance, so it only makes sense to check whether your factor explains a significantly large amount of variance.)
The "Motivating Example" section of the Wikipedia entry provides some very nice illustrations of factors that explain very little, some, and a lot of the overall variance.
Two-way ANOVA and interactions, as in your example, as well as ANCOVA, are then just generalizations on this theme. In each case, we investigate whether adding some explanatory variable explains a significantly large amount of variance.
Once we have a significant overall $F$ test, we can examine whether certain factor levels' observations are significantly different than others in post-hoc tests. For instance, D may be different from A, B and C, but those may not be significantly different from each other. You will typically use $t$ tests for this. This earlier question may be useful, as well as this one.
