The self-assembly of surfactant molecules from aqueous solutions exhibits anomalous and as yet unexplained temperature dependence. These effects include (a) a decrease in surfactant solubility, (b) an increase of the critical micelle concentration, and (c) increasing self-assembly on solid surfaces with increasing temperature near ambient temperature. These are the opposite of what one intuitively expects based on increasing molecular motion with temperature, and of what is observed for simpler fluids. Using a lattice gas theory that allows for inhomogeneity, hydrogen bonding, and micelle formation, we show conclusively that all of these phenomena arise from hydrogen bonding between water and the surfactant headgroups. While theory and experiment show very good qualitative agreement when such H bonding is included, its omission leads to complete reversal of the temperature dependence.