Why does NAD+ become reduced if it gains a hydrogen proton?

You are correct that reduction is simply a gain of electrons. This results in a decrease in oxidation number.

You know that NAD⁺ is reduced by this process because it starts off with a positive charge (+1) and ends up with a neutral charge (0).

The reducing agent that is donating the electrons is the hydrogen. More correctly, the electrons come from the hydride (H^-).

The hydride is represented by 2 electrons on this redox diagram:

As you can see, the reduction reaction transfers a proton (H⁺) and hydride electrons (H^- or 2e^-) to NAD⁺. One electron goes to the nitrogen, and the other to the carbon where the proton binds. More details on the redox reaction of NAD can be found here.