What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof?

I am uncertain of that particular proof, but I know a few proofs of Bertrand's Postulate. Bertrand's says that for all $n > 3$, there is a prime between $n$ and $2n$. In particular, this means that given a prime $p_0$, there is another prime $p_1$ s.t. $p_0 < p_1 < 2p_0$ As $2 < p_0$, we then have that there is a $p_1$ s.t.

$$p_0 < p_1 < 2p_0 < p_0 ^2$$

I think the Wikipedia proof is not so bad. Bertrand actually proved his conjecture himself in the late 1800's, and there are many proofs. Ramanujan made one, Erdos improved up it. There are also many better results and asymptotic results - I have used Pierre Dusart's improvement before, which says that for sufficiently large x (larger than 3275), there is a prime between $x$ and $x + \dfrac{x}{1 + 2\log^2 x}$. That's very intense!

But that idea is somewhat deep, and it relates to the Prime Number Theorem on the distribution of primes (which I would call very deep).