When composing two rotations, it is useful to know that a rotation about $\alpha$ about an axis $\ell$ can be written as the composition of two reflections in planes containing $\ell$, the first being chosen arbitrarily and the second being at an (oriented) angle $\frac\alpha2$ with respect to the first. Now in the composition of $4$ reflections you get, you can make your choices so that the second and third planes of reflection (the second reflection for the first rotation and the first reflection for the second rotation) are both equal to the unique plane passing through the two axes. Then poof!, those second and third reflections annihilate each other, and you are left with the composition of the first and the fourth reflection, which is a rotation with axis the intersection of those planes, and angle twice the angle between those planes.
If you want to calculate the axis and angle in terms of the original angles, formulas get a bit complicated (even for very easy choices of initial axes as in the question), but such is life, the concrete answer isn't really very easy to write down or remember.
I understand your statement now. I will summarize my answers here.
As I mentioned in my comments, $A$ is a rotation matrix since it can be written in the "standard" form under the new basis. In other words, it rotate any vector about the axis that is in the direction of $u_1$.
Notice that this last statement "it rotate any vector about the axis that is in the direction of $u_1$" is independent of the basis.
Your statement "to prove that there's a rotation such that for an orthonormal basis, applying the rotation to vectors of that basis gives A1, A2 and A3" is also correct. Because it also says the columns of $A$ is an orthonormal basis, which is true. But I think this is kind of a confusing way to prove a matrix is a rotation. Also you'll have to construct another rotation to prove it. And in what form would you construct another rotation?
A more straightforward way, as above, is to prove that the matrix $A$ rotates vectors.
Edit:
This is with regard to the matrix $A$ represented in terms of basis $u_1, u_2, u_3$. We can write a linear transformation $T$ as a matrix in terms of any basis using the following way. Given basis $e_1, e_2, e_3$, the matrix in terms of this basis is calculated by
$$[Te_1\quad Te_2 \quad Te_3]$$
where $Te_i$ is the column coordinate vector after you apply $T$ to $e_i$ in terms of this basis.
Looking at the question in this way, we see that $Au_1=\begin{pmatrix}1\\0\\0\end{pmatrix}$, $Au_2=\begin{pmatrix}0\\ \cos\theta\\ \sin\theta\end{pmatrix}$, $Au_3=\begin{pmatrix}0\\ -\sin\theta\\ \cos\theta\end{pmatrix}$.
Then
$$\begin{bmatrix}
1 & 0 & 0 \\
0 & \cos\theta & -\sin\theta \\
0 & \sin\theta & \cos\theta \\
\end{bmatrix}$$
is exactly the matrix $A$ in terms of the basis $u_1, u_2, u_3$.
Best Answer
In general, for $n\times n$ matrices $A,B$, the matrix product $AB$ represents the composite map obtained by applying $B$ first then applying $A$. This is simply because for any vector $v$, $ABv=A(Bv)$, so multiplication by $B$ is done first.
No, this is not correct the way it is written. What does it even mean for a matrix to be "rotated" about an axis? It is however true that $MR_z$ corresponds to the linear transformation which first rotates the space about the $z$-axis, and then applies the linear transformation defiend by $M$. On the other hand, $R_zM$ corresponds to applying $M$ first, and then rotating about the $z$-axis. In general, these two are not the same, of course.
It would also be correct to say that $R_zM$ has column vectors which are rotated copies of the column vectors of $M$. That is, if $$M=\begin{bmatrix}\vert&\vert&\vert\\v_1&v_2&v_3\\\vert&\vert&\vert\end{bmatrix},$$ then $$R_zM=\begin{bmatrix}\vert&\vert&\vert\\R_zv_1&R_zv_2&R_zv_3\\\vert&\vert&\vert\end{bmatrix}.$$ Of course, you will observe that $R_zv_i$ is just $R_z$ applied to $v_i$, which corresponds to $v_i$ rotated about the $z$-axis (for each $i=1,2,3$). Furthermore, $MR_z$ has row vectors which are rotated copies of the row vectors of $M$. That is, if $$M=\begin{bmatrix}-&u_1&-\\-&u_2&-\\-&u_3&-\end{bmatrix}$$ then $$MR_z=\begin{bmatrix}-&u_1R_z&-\\-&u_2R_z&-\\-&u_3R_z&-\end{bmatrix}.$$ Of course, you will again recognise that $u_iR_z$ is just a rotated copy of the $u_i$, for each $i=1,2,3$.