This is not the true mathematical answer which is much more straightforward but much less intuitive, but it is a strong suggestion towards the idea that $u(x,0)$ and $\partial_tu(x,0)$ embody all information sufficient and necessary to construct the solution of the problem.
Suppose you know $u(x,0)$ and $\partial_tu(x,0)$, the differential equations gives
$\partial^2_tu(x,0)$ for free :
$$\partial^2_tu(x,0) = c^2 \partial^2_xu(x,0)\:.$$
Actually, the differential equation also says
$$\partial^3_tu(x,t) = c^2 \partial_t\partial^2_xu(x,t) =c^2\partial^2_x\partial_tu(x,t)\:.\tag{1}$$
In particular
$$\partial^3_tu(x,0) = c^2 \partial^2_x\partial_tu(x,0)\:.$$
The right-hand side is known if we know $\partial_tu(x,0)$ (we have to derive twice this function with respect to $x$), and we know it.
So knowing $u(x,0)$ and $\partial_tu(x,0)$, we also know $\partial^2_tu(x,0)$ and $\partial^3_tu(x,0)$. We can go further computing another derivative of (1):
$$\partial^4_tu(x,t) = c^2 \partial^2_x\partial^2_tu(x,t)\:.\tag{2}$$
so that
$$\partial^4_tu(x,0) = c^2 \partial^2_x\partial^2_tu(x,0)\:.$$
We know the right-hand side, so we also know $\partial^4_tu(x,0)$.
It should be evident that this series never ends: knowing $u(x,0)$ and $\partial_tu(x,0)$, the differential equation permits us to write down
all time derivatives $\partial^n_tu(x,0)$ for $n=0,1,2,3,\ldots$ just computing many $x$-derivatives of $u(x,0)$ and $\partial_tu(x,0)$
At least formally speaking, assuming that the solution admits a Taylor expansion at $t=0$, the solution is
$$u(x,t) = \sum_{n=0}^{+\infty} \frac{t^n}{n!}\partial^n_tu(x,0)$$
where the right-hand side is known as soon as we know nothing but the differential equation, $u(x,0)$ and $\partial_tu(x,0)$.
It also clear that, even if the series does not converge to the solution, knowing the first two initial conditions necessarily implies that you also know the third and the fourth one, and so on, using the equation. So you cannot fix them freely without facing some contradiction. At most two initial conditions are permitted. Whether or not they really determine a (unique) solution depends on many other mathematical regularity conditions.