I have been trying to prove the result for a couple of days, without success, so I post what I got in the meanwhile. Let me suppose throughout that $\operatorname{Gal}(E/K)\cong(\mathbb{Z}/p)^2$ (the case $E/K$ cyclic is solved by Hilbert 94).
As Franz Lemmermeyer noticed, the answer is clear when $E$ is the Hilbert class field of $K$ by the classical principal ideal theorem, so let me suppose that we are in the first non-trivial instance, namely
$$
\mathrm{cl}_K\cong\mathbb{Z}/(p)\times\mathbb{Z}/(p^2)
$$
(I am implicitely killing everything which is prime-to-$p$, since the problem is stable under restriction to one $p$-component at a time).
Lemma: If the Hilbert class field of $E$ and of $K$ coincide, namely if $\mathrm{cl}_E\cong\mathbb{Z}/(p)$, then every ideal class of $\mathrm{cl}_K$ is principal in $E$.
Proof Call $H=H_K=H_E$ the Hilbert class field of $K$ (or of $E$, by hypothesis): it has degree $p$ over $E$ and degree $p^3$ over $K$. Let $c=[\mathfrak{p}]$ be a class of order $p^2$ in $\mathrm{cl}_K$. Then its inertia degree in $H/K$ is $p^3$ but it cannot stay inert in $E/K$ because $\mathrm{Gal}(E/K)$ is not cyclic, hence it is not isomorphic to the Galois group of an extension of the finite field $\mathcal{O}_K/\mathfrak{p}$, as it would be the case if $\mathfrak{p}$ were inert. It follows that $\mathfrak{p}\mathcal{O}=\mathfrak{P}_1\cdots\mathfrak{P}_p$ and the primes $\mathfrak{P}_i$ are all conjugate under $\mathrm{Gal}(E/K)$. Hence, they all belong to the same class in $\mathrm{cl}_E\cong\mathbb{Z}/(p)$ (and an easy argument shows this class is non-trivial, but it is not needed here), and $[\mathfrak{p}\mathcal{O}_E]=[\mathfrak{P}_1]^p=[0]$. Thus the initial class $c$ capitulates, and so does every class of order $p^2$ since $c$ was arbitrary. As $\mathrm{cl}_K$ is generated by classes of order $p^2$, everything becomes principal in $E$, q.e.d
Of course, the above proof makes crucial use of the very unnatural assumption that $\mathrm{cl}_E=\mathbb{Z}/(p)$ and I quite agree with Franz Lemmermeyer that it should be possible to come up with an exemple where one element of order $p$ in $\mathrm{cl}_K$ do not capitulate, although I am been unable to do so. May be, the only thing you can save of my answer (but which is already contained in Furtwängler's paper quoted in the comments) is that the structure of the class group of $E$ plays a crucial role for your problem. On the other hand, I doubt that $K/\mathbf{Q}$ being cyclic of order $p$ tells you much.
ADDENDUM $7^\text{th}$ February $2014$
A paper with an explicit counterexample appears today on the arXiv, here and was published in 2008 in Acta Arithmetica.