Why is potential energy negative? What does that even mean?

This is really just a definition! When we ask what the potential energy of an object is, we are really asking what energy is available to be extracted. In the case of gravity: two objects separated by an infinite distance are DEFINED to have zero gravitational potential energy. As they fall together their potential energy becomes more negative, and because of the conservation of energy their kinetic energy increases so that the total energy remains zero.

The minus sign in the gravitational potential energy is really just a convention we use to keep track of energy - there is no physical meaning behind it. We could equally define it the other way round so that kinetic energy was negative!