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.