As I understand it, increasing the temperature of water causes hydrogen bonds to break. Does this mean that a decrease in temperature is required for the formation of those hydrogen bonds?
You are right, in a sense.
A more accurate statement would be that as the temperature decreases, the average lifetime of a hydrogen bond increases. Thus, on average the liquid/solid/molecule will be more stable. This is because, as you point out, hydrogen bonds are weak enough to be broken by collisions due to thermal motions (translation and rotation). They are almost always immediately formed again (in liquid), but the more frequently they are broken, the less hydrogen bonding there will be on average.
One indicator of the degree to which hydrogen bonds stay formed is the average number of hydrogen bonds over time per water. In water, this number comes out to be around 3.4 hydrogen bonds, where it could have a maximum of 4.0. Two donors and two acceptor molecules.
Thus, you can rationalize the transition from liquid water to ice in this way by considering that in ice you come quite close to the number of 4.0 hydrogen bonds per water. As you say, then, when temperature decreases, more hydrogen bonds are formed in general. I would hesitate to call it a requirement though because hydrogen bonding can take place at any temperature, but is just rarer when the temperature increases.