I see nobody has answered this yet. As Greg Martin points out, Niven/Zuckerman/Montgomery have some material on this (Section 2.6 in the Fifth Edition): Hensel's Lemma for the case $f'(r)\not\equiv 0\pmod{p}$; a slightly more general version that says that if $f'(r)\equiv 0\pmod{p}$ but you can lift the solution to a "high enough" power of $p$, then you can keep lifting it (uniquely); and a discussion of what happens in the other cases.
Hensel's Lemma. Suppose that $f(x)$ is a polynomial with integer coefficients. If $f(a)\equiv 0\pmod{p^j}$ and $f'(a)\not\equiv 0\pmod{p}$, then there is a unique $t$ (modulo $p$) such that $f(a+tp^i)\equiv 0\pmod{p^{j+1}}$.
The formula, as noted, is
$$a_{j+1} = a_j - f(a_j)\overline{f'(a)},$$
where $\overline{f'(a)}$ denotes the modular inverse of $f'(a)$ modulo $p$. This is really the modular version of Newton's Method; you can view $a_1,a_2,a_3,\ldots$ as a sequence of approximations (in the $p$-adic norm), and the sequence $(a_1,a_2,a_3,\ldots)$ yields a $p$-adic solution to $f(x)= 0 $.
What happens if $f'(a)\equiv 0 \pmod{p}$?
Edited. Consider the Taylor expansion of $f(x)$ at $a$:
$$f(a+h) = f(a) + f'(a)h + \frac{1}{2}f''(a)h^2 + \cdots + \frac{1}{n!}f^{(n)}(a)h^n,$$
where $n$ is the degree of $f$. Note that a term $c_kx^k$ in $f(x)$ will result in
$$\frac{k(k-1)(k-2)\cdots(k-j+1)}{j!}c_kx^{k-j} = \binom{k}{j}c_kx^{k-j}$$
in $\frac{1}{j!}f^{(k)}(x)$; this has integer coefficients, so each of the coefficients $\frac{1}{j!}f^{(j)}(a)$ is an integer if $f(x)$ has integer coefficients and $a$ is an integer.
Now assume that $f(a)\equiv 0 \pmod{p^j}$ and $f'(a)\equiv 0 \pmod{p}$; then $f(a+tp^j)\equiv f(a)\pmod{p^{j+1}}$ for all integers $t$, since we have:
$$f(a+tp^j) = f(a) + tp^jf'(a) + \frac{t^2p^{2j}f''(a)}{2} + \cdots + \frac{t^np^{nj}f^{(n)}(a)}{n!},$$
and $\frac{f^{(k)}(a)}{k!}$ is an integer.
So if $f(a)\equiv 0\pmod{p^{j+1}}$, then $f(a+tp^j)\equiv 0\pmod{p^{j+1}}$ for all $t$. That is: if the solution lifts, then the single root modulo $p^j$ lifts to $p$ roots modulo $p^{j+1}$. If $f(a)\not\equiv 0\pmod{p^{j+1}}$, then none of the integers that lie above $a$ modulo $p^{j+1}$ can be roots, and there are no roots lying above $a$.
So either you can lift to all residue classes modulo $p^{j+1}$ that are above $a$, or to none.
If the power of $p$ that divides $f(a)$ is sufficiently high compared to the power of $p$ that divides $f'(a)$, then you can still rescue "lifting":
Generalized Hensel's Lemma. Let $f(x)$ be a polynomial with integral coefficients. Suppose that $f(a)\equiv 0 \pmod{p^j}$, $p^{\tau}||f'(a)$, and that $j\geq 2\tau+1$. If $b\equiv a \pmod{p^{j-\tau}}$, then $f(b)\equiv f(a)\pmod{p^j}$ and $p^{\tau}||f'(b)$. Moreover, there is a unique $t$ (modulo $p$) such that $f(a+tp^{j-\tau})\equiv 0 \pmod{p^{j+1}}$.
Above, $p^{\tau}||f'(a)$ means that $p^{\tau}|f'(a)$, but $p^{\tau+1}$ does not divide $f'(a)$. If $\tau=0$, then we get Hensel's Lemma.
Proof. If $f(a)\equiv 0\pmod{p^j}$, then plugging in $b=a+tp^{j-\tau}$ into the Taylor expansion and considering the equation modulo $p^{2j-2\tau}$, we have
$$f(b) = f(a+tp^{j-\tau}) \equiv f(a) + tp^{j-\tau}f'(a)\pmod{p^{2j-2\tau}},$$
and $p^{j+1}$ divides the modulus (since $j-2\tau\geq 1$). So
$$f(a+tp^{j-\tau}) \equiv f(a) + tp^{j-\tau}f'(a)\pmod{p^{j+1}}.$$
Both $f(a)$ and $p^{j-\tau}f'(a)$ are divisible by $p^j$ (since $f'(a)$ is divisible by $p^{\tau}$), so $f(b)\equiv f(a)\equiv 0\pmod{p^j}$. If we divide by $p^j$, we have
$$\frac{f(b)}{p^j} = \frac{f(a+tp^{j-\tau})}{p^j} \equiv \frac{f(a)}{p^j} + \left(\frac{f'(a)}{p^{\tau}}\right) t\pmod{p}.$$
The coefficient of $t$ is not divisible by $p$ (since $p^{\tau+1}$ does not divide $f'(a)$), so there is a unique value of $t$ modulo $p$ for which the right hand side is $0$ modulo $p$. This gives the final clause of the theorem. Finally, since $f'(x)$ is a polynomial with integer coefficients,
$$f'(a+tp^{j-\tau}) \equiv f'(a)\pmod{p^{j-\tau}}$$
for all $a$; and $j-\tau\geq \tau+1$, so the congruence also holds modulo $p^{\tau+1}$. Since $p^{\tau}$ divides $f'(a)$ but $p^{\tau+1}$ does not, then $p^{\tau}$ divides $f'(a+tp^{j-\tau})$ but $p^{\tau+1}$ does not. $\Box$
So once you get past a certain point, you can continue lifting as with Hensel's Lemma.
Niven/Zuckerman/Montgomery then show this at work with $x^2+x+223\equiv 0\pmod{3^j}$.
Modulo $3$,t he only solution is $x=1$. $f'(1)=3\equiv 0\pmod{3}$, and $f(1)\equiv 0\pmod{9}$, so each of the three congruence classes lying above $1$, namely $1$, $4$, and $7$, are roots modulo $9$. Since $f(1)\not\equiv 0\pmod{27}$, then $1$ does not lift to solutions modulo $3^3$. Same thing with $f(7)$. On the other hand, $f(4)\equiv 0 \pmod{27}$, so we get three roots modulo $27$, namely $4$, $13$, and $22$. Each of these is still $0$ modulo $81$, so each of these lifts to three solutions modulo $81$. That is, we have nine solutions modulo $81$, namely $4$, $31$, and $58$ (lying over $4$); $13$, $40$, and $67$ (lying over $13$); and $22$, $49$, and $76$ (lying over $22$).
Since $f(4)\equiv 0 \pmod{3^5}$ and $3^2||f'(4)$, we get nine solutions of the form $4 + 27t$ modulo $243$; but there is exactly one value of $t$, $t=2$, for which $4+27t$ is a root modulo $3^6$. So we get nine solutions modulo $3^6$, which are of the form $(4+27(2)) + 81t = 58+81t$.
Similarly, $f(22)\equiv 0\pmod{3^5}$, $3^2||f'(22)$, and so there are nine solutions of the form $22+27t$ modulo $3^5$; there is precisely one value of $t$, namely $t=0$, for which $22+27t$ is a solution modulo $3^6$, which gives nine solutions modulo $3^6$ lying above $22$, the ones of the form $22+81t$.
Finally, $f'(13)\equiv 0 \pmod{27}$, so $f(13+27t)\equiv f(13)\pmod{3^6}$, but $3^4||f(13)$, so none of the integers $13+27t$ modulo $81$ lift to solutions modulo $243$.
After this point, we can apply the generalized Hensel's Lemma: for each $j\geq 5$, there are precisely 18 solutions modulo $3^j$, of which 12 do not lift to $3^{j+1}$ and each of the remaining six lifts to three solutions each.
In summary: if $f(a)\equiv 0 \pmod{p}$, and $f'(a)\equiv 0\pmod{p}$, to determine if $a$ can be lifted to solutions modulo arbitrarily large powers of $p$, determine if you can reach the point where the Generalized Hensel's Lemma applies, i.e., when $j\geq 2\tau+1$. It can be shown that the inequality holds whenever $j$ is larger than the highest power of $p$ that divides the discriminant of $f$.
Best Answer
Yes, when Hensel's lemma applies, it gives all solutions.
One way to see why (the simplest form of) Hensel's lemma is true is nothing more than simply solving the equation
$$ f(x + a p^k) \equiv 0 \pmod{p^{k+1}} $$
for $a$ in a situation where $f(x) \equiv 0 \pmod{p^k}$ and the Taylor series for $f(x)$ makes sense and the higher order terms vanish, due to the high powers of $p$ involved:
$$ f(x + a p^k) \cong f(x) + a p^k f'(x) \pmod{p^{k+1}} $$