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: 
You almost answered your own question. If you increase potential energy by going up, then you decrease by going down. Decreasing means becoming more negative. So, being in a gravity well causes an object to have less total energy than an object not in a gravity well, all else equal. If you say 0 potential energy due to gravity is at a place far far away from any gravity well, then it must be negative in a gravity well. That means you have to pay energy to climb out of a well.
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.