Given that one can sample unitaries from the Haar measure over $U(n)$ (as in F. Mezzadri, Notices of the AMS 54 (2007), 592604), how can one sample from the uniform distribution over the following subgroup, $$ \mathcal{B} = \{ A \in U(n) : [A, B] = 0 \}, $$ where $B$ is another, fixed unitary in $U(n)$?
I assume all eigenvalues of $B$ are distinct, so that $B$ has a unique set of eigenvectors. Because of the constraint $[A,B]=0$, you wish to sample over unitary matrices $A$ that have the same set of eigenvectors as $B$, hence only the eigenvalues $e^{i\phi_1},e^{i\phi_2},\ldots e^{i\phi_n}$ of $A$ matter. To achieve uniformity (meaning for any $A$ and $C$ in ${\cal B}$ both $A$ and $AC$ are sampled with the same probability) the distribution of the phases should leave $P(\phi_1,\phi_2,\ldots\phi_n)$ invariant when any $\phi_k\mapsto \phi_k+\delta\phi$, $k\in\{1,2,\ldots n\}$, for arbitrary increment $\delta\phi$. To ensure that, take uniform distributions in $(0,2\pi]$, independently for each $\phi_k$.

1$\begingroup$ Thanks! That is very helpful. If I understand it correctly, you are saying that $A$ must be block diagonal in the eigenbasis of $B$, and to sample from the Haar measure on the Lie subgroup $\mathcal{B}$, one can sample each block of $A$ (which are also unitaries) from the Haar measure separately, and then put them together. Naively this satisfy the uniformity condition. $\endgroup$ – liydsl2 Jun 28 '18 at 6:28