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.