Does this method uniformly sample 3x3 rotation matrices?

Let $\textbf{X}=(X_1,X_2,X_3)$ be a random unit vector in $\mathbb{R}^3$ such that $\textbf{X}$ is uniformly distributed on the unit sphere $S^2$. Next, let $\textbf{Y}=(Y_1,Y_2,Y_3)$ be a random unit vector that is orthogonal to $X$ and then define $\textbf{Z} = \textbf{X}\times \textbf{Y}$.

Finally, define $\textbf{R} = (\textbf{X},\textbf{Y}, \textbf{Z})$ to be the rotation matrix that maps $\textbf{e}_1\mapsto \textbf{X}$, $\textbf{e}_2\mapsto \textbf{Y}$, $\textbf{e}_3\mapsto \textbf{Z}$.

Is $\textbf{R}$ a uniformly random orientation-preserving rotation matrix? In more technical parlance, is the probability measure induced by $\textbf{R}$ the normalized Haar measure on $SO(3)$? And if so (or not), why?

Setting aside for a moment whether your sampling procedure in fact samples from the Haar measure on $SO(3)$, it samples from some distribution on $SO(3)$. To show that this measure is (proportional to) Haar measure, we need to show that it is left invariant.

Now, there is a natural map $SO(3) \rightarrow S^2$ which takes an orthogonal matrix to its first column. The fiber of this map (inverse image) over any point $v$ in $S^2$ is the collection of vector pairs $(v_1, v_2)$ in $R^3$ that together with $v$ form an oriented basis. The first vector $v_1$ is clearly confined to the circle $S^1$ of unit vectors orthogonal to $v$, and once $v_1$ is known, the identity of $v_2$ is forced by the orientation condition. So, each fiber of the projection mapping is an $S^1$.

Your sampling procedure can be summarized in this setting as

• First sample a point $v$ from the uniform measure on the unit sphere $S^2$.
• Then sample a point from the uniform measure on the fiber over $v$, which is isometric to a unit circle.

The uniform measures on $S^2$ and $S^1$ are induced from the standard Riemannian metrics from $R^3$ (they are proportional to the volume measure). So, if we can show that an orthogonal transformation maps $S^2$ isometrically to itself, and the fiber over and point $v$ isometrically onto the fiber over its image, then we are done.

An Orthogonal Transformation Maps the Unit Sphere Isometrically to Itself:

Let $v, w$ be two unit vectors in $S^3$, and let $O$ be an orthogoal matrix. Then

\begin{align} |v - w|^2 &= (v - w)^t (v - w) \\ &= (v - w)^t O^t O (v - w) \\ &= (Ov - Ow)^t (Ov - Ow) \\ &= |Ov - Ow|^2 \end{align}

So $O$ is a self isometry of $S^2$.

An Orthogonal Transformation Maps the Fibers Isometrically:

First, since orthogonal transformations preserve orthogonality between vectors, an orthogonal transformation $O$ does in fact map the fiber over a vector $v$ to the fiber over $Ov$. To show this mapping is isometric, we only need to repeat the calculation given above for the $S^2$ case with two vectors orthogonal to $v$. Since the angle between these vectors is preserved, the arc length between them is as well, and hence one circle is mapped isometrically to the other.

So, the metric induced from your sampling procedure is left invariant, and hence you are sampling from the Haar measure on $SO(3)$.