Q:

How to interpret the p-value in this toy example (two coin tosses)

The p-value is said to be the probability of the respective event assuming that $H_0$ is true. The simplest possible toy example are two coin tosses. The 2-tailed $H_0$ would be that you consider the coin fair, $H_1$ in this case is that you consider it biased to one side or the other.
For one 1-tailed test $H_0$ would be that it is either fair or biased towards e.g. heads. $H_1$ would then be that you consider it biased towards tails (the other side) in this case. 
You can experiment with this toy example in R, first the two-tailed case:
> binom.test(2,2,alternative="two.sided")

    Exact binomial test

data:  2 and 2
number of successes = 2, number of trials = 2, p-value = 0.5
alternative hypothesis: true probability of success is not equal to 0.5
95 percent confidence interval:
 0.1581139 1.0000000
sample estimates:
probability of success 
                     1

And now for the one-tailed case: 
> binom.test(2,2,alternative="greater")

    Exact binomial test

data:  2 and 2
number of successes = 2, number of trials = 2, p-value = 0.25
alternative hypothesis: true probability of success is greater than 0.5
95 percent confidence interval:
 0.2236068 1.0000000
sample estimates:
probability of success 
                     1 

My question is: What is the correct interpretation of the p-value in the latter case?
Here you assume under $H_0$ that the coin is either fair or biased towards one side but get a result which seems to be biased towards the other side. But the p-value says $0.25$ which is not the probability under the condition $H_0$ but again assuming a fair coin (one coin combination out of four possible results assuming a fair coin) - as in the two-tailed case! Is this in some way connected to the fact that you effectively halved your p-value by going from two-tailed to one-tailed although you threw the exact same (!) combination in both cases?

A:

Your first statement is incorrect: the p-value is not the probability of the observed outcome assuming that $H_0$ is true, but the probability of observing an event as extreme or more extreme than the observed outcome. The definition of "extreme" depends on the null and alternative hypotheses. We try to gather all events that would provide the same or more evidence against the null hypothesis in favor of the alternative.
In your example, for a one-sided test $H_0: p(Heads)=0.5$ vs $H_a: p(Heads) > 0.5$, observing $HH$ is the most extreme evidence in favor of $H_a$, so the p-value is $P(HH | H_0)=0.25$. For a two-sided test with $H_a: p(Heads) \neq 0.5$, observing $TT$ provides the same amount of evidence against $H_0$ as $HH$, so the p-value is $P(HH \text{ or } TT | H_0) = 0.5$. 

