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.
OK Drop a 10 kg object from a height of 10 meters. It will gain speed as it falls, and so kinetic energy. At the bottom, catch it in such a way that you charge a battery by using the kinetic energy and bring it to stop.

Just by making the object fall for 10 meters, you were able to collect some energy. This energy comes from somewhere - and that is decrease in gravitational potential.

The decrease means negative.

As we know that same object would not fall by itself in far space, we can not collect energy in this way, or we can say we can only collect 0 energy. So, the the gravitational potential in far space is 0. If you decrease something from 0, it becomes negative. If you increase something from negative, it will reach 0.

But if your question refers to why it is negative in philosophical sense - means there is no such thing as negative energy. Then I agree, it is a "decrease", not "negative". The "decrease" itself is a real (positive) amount. negative amounts are not real even though negative numbers are real numbers. For example, there is no such thing as -5 kg mass. You can decrease mass of a 10 kg mass object by 5 kg by taking 5 kg mass away. But that 5 kg will remain a 5 kg mass wherever you take it. There is no -5 kg mass. 

Therefore it is "decreased" gravitational potential of the combined (earth and object) system, which is written as negative potential.

When the object is in far space, the 0 potential refers only to the object because earth is not in the picture in that case. Only when it comes in earth's gravitational influence, we start talking about the potential of the combined system. 

While saying 0 potential of the object in far space, I am ignoring the small potential of the object due to its own constituent mass. 

"Point B higher than A" means you have to spend energy in moving from point A to B. This way you are adding energy to the potential of the system and so, the total potential increases. (say from -10 at A to -5 at B). -10 at A means you have to spent 10 units of energy in moving from A to far space. -5 at B means you have to spend 5 units of energy in moving from B to far space. So negative potential at a point is actually amount of positive energy you have to spend in moving from that point to far space. Conversely, when you move from far space to A, you gain 10 units of kinetic energy. B is at a higher potential (-5) than A (-10). Higher potential of B means you have to spend lesser amount of energy to move from B to far space. That is why it is -5 at B and considered higher than -10 at A. Give it few days to think multiple times and you will get it. Trying to get it in one go may not be as productive.