Find out all solutions of the congruence $x^2 \equiv 9 \mod 256$.

You can't reason from $256\mid ab$ to $256\mid a \lor 256\mid b$ because $256$ is not a prime. Instead you need to consider all the ways that the prime factors of $256$ can be distributed among $a$ and $b$.

Since $256$ is a prime power, namely $2^8$, there are only nine ways to write it as a product, and we can check those systematically:

Case 0. $256\mid(x-3)$ and $1\mid(x+3)$. This leads to the solution $x=3$.

Case 1. $128\mid(x-3)$ and $2\mid(x+3)$. The former implies the latter, so this leads to the solution $x=131$ as well as $x=3$ which we already know.

Case 2. $64\mid(x-3)$ and $4\mid(x+3)$. This would require the difference between $x-3$ and $x+3$ to be a multiple of $4$, which is never the case, so this is impossible.

Case 3. $32\mid(x-3)$ and $8\mid(x+3)$. Similar to case 2 -- impossible because $6$ is not a multiple of $8$.

Cases 4 through 6. Similar.

Case 7. $2\mid(x-3)$ and $128\mid(x+3)$. This gives $x=125$ or $x=253$.

Case 8. $1\mid(x-3)$ and $256\mid(x+3)$. This gives $x=253$, which we already know from case 7.

So the solutions are $\{3,125,131,253\}$.

You know that

$$(\Bbb Z/256\Bbb Z)^\times\cong \Bbb Z/2\Bbb Z \times \Bbb Z/64\Bbb Z$$

and Hensel's lemma gives a lifting for solutions if you can find them modulo $8$ and unique lifts. Since there are $4$ solutions modulo $8$, these lift to $4$ solutions modulo any higher power of $2$.

Edit: Since the op doesn't know Hensel, it's easy enough to just use the isomorphism directly, the square are index $4$, so if there is any square root, there are $4$ of them since any different ones differ by an element of the kernel of the squaring map.