Why does Gaussian elimination not preserve similarity of a matrix?

In the Gaussian elimination, given a matrix $A$, you apply a sequence of elementary row operations $E_1,\ldots,E_k$ in order to obtain a row echelon form $B$ of $A$: $$\tag{1} B=E_k\cdots E_1A=:EA. $$

Two matrices $A$ and $B$ are similar if and only if there is a nonsingular $X$ such that $$\tag{2}B=XAX^{-1}.$$ So there is no good reason why $A$ and $B$ in (1) should be similar (unless, of course, $E=I$).

If you want to preserve similarity using the elementary operations used in Gaussian elimination, you need to apply them "symmetrically", e.g., having an elementary operation $\tilde{E}$, $\tilde{E}A\tilde{E}^{-1}$ is a similarity transformation of the form (2) (note that the elementary row operations are easily invertible).

Considering the reduction to the Hessenberg form, while you zero out the part of the matrix below the first subdiagonal, each row operation has to be coupled by applying its inverse from the right.

You can use Gauss to take the matrix \begin{equation} \left( \begin{array}{cc} 1 & 0\\ 1 &1 \end{array} \right) \end{equation} To the identity matrix. Since the identity similar only to itself, Gauss elimination does not respect similarity.