How to determine which gas is more soluble
You could answer this question by looking at the possible interactions between a gas molecule and water molecules. The only I can see are van der Waals interactions (because these gas molecules cannot participate in hydrogen bonding).

$\ce{O_2}$ and $\ce{Br_2}$ have no permanent dipole so the only interactions are Debye forces (interaction between water permanent dipole and a gas molecule induced dipole) and London forces (between instantaneous dipoles).

The induced/instantaneous dipoles strength increases with the size of the atom because the bigger the electron cloud the easier it is to modify its shape.It happens because the electrons far away from the nucleus are less attracted by it and can move around a bit more easily than electrons very close to the nucleus.

This is the reason why van der waals forces are stronger for bigger atoms.
This would explain why $\ce{Br_2}$ has a better solubility than $\ce{O_2}$ in water.

As a side note:

London interactions are very important if you look at liquefaction temperature of gases. For instance, it explains why $\ce{Ar}$ becomes a liquid below 87K while $\ce{He}$ become a liquid only below 4K.