Strong induction is induction where you assume that all previous cases satisfy your induction hypothesis, not just the most recent case. Sometimes knowing the previous step just isn't enough. The following well-known theorem is a good example of strong induction: Every natural number factors into a product of irreducibles.
Base case: $n=2$ factors into irreducibles. Now, for the induction step, suppose all numbers less than or equal to $n-1$ factor into irreducibles. Now either $n$ is irreducible, or $n=kl$, where $k$ and $l$ are less than $n$. Now since I can write $k$ and $l$ each as a product of irreducibles (by the induction hypothesis), I can write $n$ as a product of irreducibles.
Note that it would not have been good enough to assume the induction hypothesis only for $n-1$, since knowing that $n-1$ factors tells me nothing about whether $n$ factors. Instead, in my induction hypothesis I assumed all natural numbers less than $n$ factor.
EDIT: Note that irreducible numbers are the same as prime numbers. See the discussion below if you're wondering about my choice of terminology.