 Solution

Fix a Borel subgroup $B$ and a maximal algebraic torus $T\subset B$. Conjugacy of Borel subgroups and the equality $N_G(B)=B$ identify the flag variety with $G/B$, by $gB\mapsto {}^{g}B$.

Every simultaneous conjugacy orbit on pairs contains a pair $(B,{}^{g}B)$: first conjugate its first member to $B$. The remaining allowed conjugations are by $B$. Two such pairs are in the same orbit exactly when $g^{\prime }$ belongs to $BgB$. Indeed ${}^{g^{\prime }}B={}^{bg}B$ is equivalent to $(bg{)}^{-1}{g}^{\prime }\in N_G(B)=B$. Thus there is an explicit bijectionThe Bruhat decomposition is the disjoint partition $G={\coprod }_{w\in W}B\dot{w}B$, with $W=N_G(T)/T$. Under the displayed bijection its double coset $B\dot{w}B$ becomes the orbitThis proves that the orbits are indexed by the Weyl group. Conversely, the assertion that these particular $O(w)$ exhaust the orbits without repetitions says precisely that the $B\dot{w}B$ exhaust $G$ without repetitions. Hence the orbit description and the Bruhat decomposition are equivalent, not merely two sets of the same cardinality. Their common index is the relative position of Borel subgroups.