I'll address the case $e=2$; if $\gcd(e, \phi(n)) = 2$, then this is sufficient (as it would suffice to find the squareroot of $c$ (the ciphertext), and then take the $e/2$th root of that.
So, we're given $c$ and want to find the values $m$ s.t. $m^2 = c \pmod {p^2}$.
We start by finding the values $m'$ s.t. $m'^2 = c \pmod p$; this is a modular squareroot, and there are known algorithms for it. The easiest applies if $p \equiv 3 \pmod 4$; in that case, $m' = \pm c^{(p+1)/4} \bmod p$. The $p \equiv 1 \pmod 4$ case is also doable, but is more work.
Given those values, we convert those into values modulo $p^2$. That turns out to be even easier, because if we have $m = m' + xp$ (and $m$ will always be equivalent to one of the $m'$ values modulo $p$), then we have:
$$m^2 = (m' + xp)^2 = m'^2 + 2m'xp = c \pmod {p^2}$$
And, since $c-m'^2$ is a multiple of $p$, we can reduce this to:
$2m'x = (c - m'^2)/p \pmod p$, or $x = (2m')^{-1} (c - m'^2)/p \pmod p$
And, $m = m' + px$ gives you the values of $m$ (and remember, there are two possible values of $m'$ and hence two possible values of $m$).
Also note that, because we managed to do with without any private information, this doesn't work as 'public key encryption'
