Question: How can gravitational potential be negative?

Gravitation energy increases as we go higher. How is this possible when it is negative?

Please give an intuitive explanation.
Actually I'm confused by this statement: "Gravitational potential energy increases as we go higher but still remains negative." 

My doubt is almost cleared by all of your explanations (thanks, btw), but there is still one thing:- Consider two points A and B and B higher than A. Gravitational potential energy is lower at A that is it's more negative or in other words potential energy at B is closer to zero or less negative. But **magnitude of the potential energy at A is greater than B**, that is the absolute value is more for A but still it's at lower potential. This is what I always end up thinking and get confused. I have not got any satisfactory answer to this question :(

Answer: 
Around a point-like object, the gravitational potential is singular as the distance decreases to zero, thus you can't use it as a ground potential.

The only meaningful alternative to use the infinite distance as zero potential.

But, to preserve energy, objects coming from near-infinite, they get kinetical energy, this is coming by the decrease in the gravitation well. Thus the gravitational energy should be negative.

If you revert the convention, i.e. to have a positive gravitational potential, then

1. you should revert also the kinetical energy. It is weird
2. or you have to find a different zero reference point (it also weird + occasional, you have to explain, why)
3. or you will harm energy preservation (-> give up useful physics)

Note, if you calculate some easy thing, for example you are calculating the gravitational energy of an elevator in a high school homework task, you can use the ground as zero reference without any problem. It falls to (2): you essentially selected 6636km distance as zero potential in the gravity well of the Earth.
The only thing that matters for the movement of particles (in classical mechanics) are potential differences between different points. The Force $\vec{F}=-\text{grad}\ V$ where $V$ is the potential. A constant term in the function $V(x)$ will not affect the force and is physically meaningless. It does not matter what the value of the potential is and the value itself need not be interpreted physically.