If $\lambda_1$ an eigenvalue of $A$ with associated eigenvector $u_1$ (unitary), we can get an orthonormal basis of $\mathbb{C}^3:$ $B=\left\{u_1,u_2,u_3\right\}$ so, $U_1=\begin{bmatrix}u_1,u_2,u_3\end{bmatrix}$ is an unitary matrix. Besides $Au_1=\lambda_1u_1$, hence $$AU_1=A\begin{bmatrix}u_1,u_2,u_3\end{bmatrix}=\begin{bmatrix}\lambda_1u_1,Au_2,Au_3\end{bmatrix}$$ $$=\begin{bmatrix}u_1,u_2,u_3\end{bmatrix}\begin{bmatrix} \lambda_1 & * & * \\ 0 & * & *\\ 0 & * & * \end{bmatrix}=U_1\left[\begin{array}{c|c}
\lambda_1 & b_1 \\ \hline
0 & A_1
\end{array}
\right].$$ That is, $$U_1^{-1}AU_1=\left[\begin{array}{c|c}
\lambda_1 & b_1 \\ \hline
0 & A_1
\end{array}
\right],\text{ with } U_1 \text{ unitary and } A_1\in\mathbb{C}^{2\times 2}.$$ If you find $M_2\in \mathbb{C}^{2\times 2}$ unitary such that $M_2^{-1}A_1M_2=\begin{bmatrix} \lambda_2 & t_{12} \\ 0 & \lambda_3 \\\end{bmatrix},$ define $$U_2=\left[\begin{array}{c|c}
1 & 0 \\ \hline
0 & M_2
\end{array}
\right].$$ $U_2$ is unitary and $$\left(U_1U_2\right)^{-1}A\left(U_1U_2\right)=U_2^{-1}U_1^{-1}AU_1U_2$$ $$=\left[\begin{array}{c|c}
1 & 0 \\ \hline
0 & M_2^{-1}
\end{array}
\right]U_1^{-1}AU_1\left[\begin{array}{c|c}
1 & 0 \\ \hline
0 & M_2
\end{array}
\right]$$ $$=\left[\begin{array}{c|c}
1 & 0 \\ \hline
0 & M_2^{-1}
\end{array}
\right]\left[\begin{array}{c|c}
\lambda_1 & b_1 \\ \hline
0 & A_1
\end{array}
\right]\left[\begin{array}{c|c}
1 & 0 \\ \hline
0 & M_2
\end{array}
\right]$$ $$=\left[\begin{array}{c|c}
\lambda_1 & b_1 \\ \hline
0 & M_2^{-1}A_1
\end{array}
\right]\left[\begin{array}{c|c}
1 & 0 \\ \hline
0 & M_2
\end{array}
\right]=\left[\begin{array}{c|c}
\lambda_1 & b_1M_2 \\ \hline
0 & M_2^{-1}A_1M_2
\end{array}
\right]$$
$$=\begin{bmatrix} \lambda_1 & s_{12} & s_{1n}\\ 0 & \lambda_2 & s_{2n} \\ 0 & 0 &\lambda_3\end{bmatrix}=T.$$ The matrix $U=U_1U_2$ is unitary (product of unitary matrices), as a consequence $U^{-1}AU$ $=$ $U^*AU=T$ with $T$ triangular.
Suppose $A, T, Q \in \mathbb{R}^{n \times n}$, $A=Q T Q^T$, $A$ and $Q$ are orthogonal. Then $T$ is orthogonal. We want to prove that if $T$ is quasitriangular, then it's quasidiagonal. This follows from the following theorem.
Theorem
Suppose
$$T=\begin{bmatrix}
B_{1,1} & B_{1,2} & \dots & B_{1,m} \\
& B_{2,2} & \dots & \vdots \\
& & \ddots & \vdots \\
& & & B_{m,m}
\end{bmatrix}$$
is a real orthogonal or complex unitary block matrix, where each $B_{i,i}$ is a $1 \times 1$ or a $2 \times 2$ matrix. Then for each $i$ for each $j>i$ we have $B_{i,j}=0$.
Proof of the theorem
Since T is orthogonal or unitary, we have $T^* T = I$, which can be visualized as
$$\begin{bmatrix}
B_{1,1}^* & & & \\
B_{1,2}^* & B_{2,2}^* & & \\
\vdots & \vdots & \ddots & \\
B_{1,m}^* & \dots & \dots & B_{m,m}^*
\end{bmatrix}
\cdot
\begin{bmatrix}
B_{1,1} & B_{1,2} & \dots & B_{1,m} \\
& B_{2,2} & \dots & \vdots \\
& & \ddots & \vdots \\
& & & B_{m,m}
\end{bmatrix}
=
\begin{bmatrix}
I&&& \\
&I&& \\
&&\ddots& \\
&&&I
\end{bmatrix}.
$$
Now we will prove by induction on $i$ that for each $i$, $B_{i,i}^*$ is invertible and for each $j > i$ we have $B_{i,j}=0$.
Base of induction: it can be seen from the structure of matrices in the equation above that $B_{1,1}^* B_{1,1} = I$ and thus $B_{1,1}^*$ is invertible, and that for each $j>1$, $B_{1,1}^* B_{1,j}=0$, which by invertibility of $B_{1,1}^*$ gives us $B_{1,j}=0$.
Inductive step. Suppose for each $i$ up to and including $k$, for each $j > i$ we have $B_{i,j}=0$. So, we have
$$\begin{bmatrix}
B_{1,1}^*&&&&&& \\
& \ddots &&&&& \\
&& B_{k,k}^* &&&& \\
&&&B_{k+1,k+1}^* & & & \\
&&&B_{k+1,k+2}^* & B_{k+2,2}^* & & \\
&&&\vdots & \vdots & \ddots & \\
&&&B_{k+1,m}^* & \dots & \dots & B_{m,m}^*
\end{bmatrix}
\cdot
\begin{bmatrix}
B_{1,1}&&&&&& \\
& \ddots &&&&& \\
&& B_{k,k} &&&& \\
&&&B_{k+1,k+1} & B_{k+1,k+2} & \dots & B_{k+1,m} \\
&&&& B_{k+2,k+2} & \dots & \vdots \\
&&&& & \ddots & \vdots \\
&&&& & & B_{m,m}
\end{bmatrix}
=
\begin{bmatrix}
I&&&&&& \\
&\ddots&&&&& \\
&&I&&&& \\
&&&I&&& \\
&&&&I&& \\
&&&&&\ddots& \\
&&&&&&I
\end{bmatrix}.
$$
From the structure of matrices in this equation we can see that $B_{k+1,k+1}^* B_{k+1,k+1} = I$, which means that $B_{k+1,k+1}^*$ is invertible, and that for each $j > k+1$ we have $B_{k+1,k+1}^* B_{k+1,j} = 0$, which by invertibility of $B_{k+1,k+1}^*$ gives us $B_{k+1,j}=0$. QED
Best Answer
Regarding the first step:
All we know about the matrix $Q_1$ is that its first column $q_1$ is an eigenvector of $A$. We are trying to prove the existence of a matrix $Q$ such that $Q^*AQ$ is upper triangular, but we're not quite there yet.
Now, consider the product $$ Q_1^*AQ_1 = \pmatrix{q_1^*\\ \vdots \\ q_n^*}\pmatrix{Aq_1 & \cdots & Aq_n} = \\ \pmatrix{q_1^*Aq_1 & q_1^*Aq_2 & \cdots & q_1^*Aq_n\\ q_2^*Aq_1 & q_2^*Aq_2 & \cdots & q_2^*Aq_n\\ \vdots & \vdots & \ddots & \vdots\\ q_n^*Aq_1 & q_n^*Aq_2 & \cdots & q_n^*Aq_n} $$ Note, however, that for complex vectors $u$ and $v$, $u^*v$ is the inner product (Hermitian inner product) of the vectors $u$ and $v$. So, since $q_1$ is an eigenvector, and since $q_1$ is orthogonal to the other $q_i$, we may rewrite the above matrix as $$ Q_1^*AQ_1 = \pmatrix{q_1^*Aq_1 & q_1^*Aq_2 & \cdots & q_1^*Aq_n\\ 0 & q_2^*Aq_2 & \cdots & q_2^*Aq_n\\ \vdots & \vdots & \ddots & \vdots\\ 0 & q_n^*Aq_2 & \cdots & q_n^*Aq_n} $$ which is precisely the desired form, if we set $t_{11} = q_1^*Aq_1$.
Regarding the second:
Using block-matrix multiplication, note that $$ \tilde Q A \tilde Q^{-1} = \pmatrix{I_{k}&0\\0&Q} \pmatrix{A_{11}&A_{12}\\A_{21}&A_{22}} \pmatrix{I_{k}&0\\0&Q}^{-1} = \pmatrix{A_{11}&A_{12}Q^{-1}\\QA_{21}&QA_{22}Q^{-1}} $$ Note that $I_k$ is the size-$k$ identity matrix, and that each of these block matrices are partitioned in the same way.
In a more abstract proof, we could build this matrix in a more immediately intuitive fashion. In particular, to build the linear transformation $\tilde Q$, first consider its restriction $Q$ to a certain invariant subspace of $A$.