The potential energy of gravitation is written U = -G\dfrac{Mm}{r}. It is negative.
It comes out negative because infinity was chosen as the reference where U = 0. The nearer a body comes, the more it is drawn in and falls, so it lies below the reference, which is to say at a negative value. This is a matter of where the reference was placed, not a sign that energy is somehow lacking.
Why not take the ground as the reference? Because mgh can only be used where g may be treated as constant, that is, just above the surface. As the height approaches the radius of the Earth, g falls off visibly and mgh stops agreeing. Infinity is the more convenient reference precisely because it still serves however far away you go.
The curve in the figure approaches 0 as r grows and plunges deeper the nearer the body. Cut out just the part of that curve immediately above the surface and it looks very nearly straight. Its slope is mg, and mgh was the equation that looked only at that stretch.
With the potential energy settled, conservation of mechanical energy can be used: \dfrac{1}{2}mv^2 - G\dfrac{Mm}{r} = E, where E has the same value everywhere on the orbit.
The horizontal line in the figure is E, the curve is U, and the vertical gap between them is the kinetic energy K. Near the body U plunges deep, so K is large and the motion is fast. The farther out, the more K shrinks.
Where the two meet, K is 0. That is the turning point, and the body can go no farther. So long as E is negative such a crossing must exist, and the orbit closes. This is why the orbit is an ellipse.
To find the speeds at the nearest and farthest points of an elliptical orbit, pair this equation with r_1v_1 = r_2v_2 from the areal velocity. Two unknowns, v_1 and v_2, and two equations, which is enough to solve.
What speed does it take to keep circling just above the surface? This is called the first cosmic velocity.
The orbit is circular, so gravitation is the centripetal force. Setting G\dfrac{Mm}{R^2} = \dfrac{mv^2}{R} and cancelling m gives v = \sqrt{\dfrac{GM}{R}}.
Recalling that g = G\dfrac{M}{R^2}, we have GM = gR^2, so this can be rewritten v = \sqrt{gR}. In that form it can be worked out from g and the radius of the Earth alone, without knowing either G or M. With the Earth's values it comes to about 7.9 kilometres per second.
Slower than this and the body falls to the ground; at this speed it keeps falling and never reaches the ground. This is the speed meant by fast enough in Newton's cannonball.
So what does it take never to come back? This is the second cosmic velocity, the escape velocity.
The boundary case is one that comes to rest exactly at infinity. There U = 0 and K = 0, so E = 0. The mechanical energy does not change, so at launch too we must have E \geq 0.
Solving \dfrac{1}{2}mv^2 - G\dfrac{Mm}{R} \geq 0 gives v \geq \sqrt{\dfrac{2GM}{R}} = \sqrt{2gR}. That is exactly \sqrt{2} times the first cosmic velocity, about 11.2 kilometres per second for the Earth.
On the left of the figure is the case that falls short: however high it climbs, its speed reaches 0 at the horizontal line and it falls back. On the right is the case that suffices: there is no height at which it stops, so it simply leaves. All that separates the two is the sign of E.