Brine is a concentrated salt solution, meaning that it is a liquid with lots of free ions in it. We have the ions from the salt, Na+ and Cl− and the ions from the water that the salt is dissolved in, H+ and OH−.
The positive ions (Hydrogen and sodium in this case) are attracted to the negative electrode (the cathode) due to having opposite charges. However, there is a rule at the negative electrode that the least reactive metal will be discharged (turned into atoms). Because hydrogen is less reactive than sodium, the hydrogen is discharged as H atoms that then bind to form H2 molecules.