Solution of the Roothaan Equations of H2 by Symmetry Arguments
After speaking to a coworker and reading some more I think I have a better understanding.
The symmetry of the wave function needs to follow the symmetry of the molecule (unless we are studying a broken symmetry solution, e.g. charge transfer, but that doesn't apply in this case). We are using a minimal basis, and hence we have only two orbitals. From atomic theory, these are s functions. Hence, they cannot form $\pi$ orbitals, and we are left with $\sigma$ orbitals. Between $\sigma_g$ and $\sigma_u$, $\sigma_g$ has the lower energy because it has no nodes, whereas $\sigma_u$ contains a node. From QM we know that this generally implies greater energy, but there's a nice explanation on this here (at the end he also specifically discusses a homonuclear diatomic molecule).
The specifics of how to get the symmetry representation for the molecule and match those with wave functions is still not entirely clear to me, but for this I will read a book on group theory and its chemical applications. It is, however, clear that $\phi_1+\phi_2$ and $\phi_1-\phi_2$ respect $\sigma_g$ and $\sigma_u$ symmetry respectively.