This is quite a long post, and it goes into a lot more detail than is perhaps necessary, but I felt it was important to be thorough. For the sake of simplicity, I'm going to restrict to linear transformations from a vector space $V$ to itself, also known as linear operators. This is really the only situation in which talking about similarity of matrices is meaningful, since it assumes that each matrix will use only one basis for both its input and its output.
Part I Setting Up the Stage
It's important to understand here in what sense $A$ and $B$ are representing the same linear transformation, and really in what sense they represent a linear transformation at all. The crucial thing to keep in mind is that each matrix is representing a particular linear transformation with respect to a specific basis. Generally, when we go writing down matrices, the basis we're working with is implicit and often it isn't even actually mentioned since there is an implicit understanding of what the basis is that we're working with. This can be quite confusing however when you learn linear algebra for the first time as it can create a lot of potential for glossing over important distinctions, or even completely failing to notice them.
In particular, what linear transformation a matrix represents will change depending on what basis you are using. That is, the same matrix will represent different linear transformations in different bases. Therefore, for $A$ and $B$ to represent the same linear transformation $T$, there has to be a basis $\beta_1$ such that $A$ represents $T$ with respect to $\beta_1$, and a basis $\beta_2$ such that $B$ represents $T$ with respect to $\beta_2$. If you happen to be considering $A$ and $B$ with respect to the same basis, then of course they will represent different transformations. (After all, they could be representing similar operators.)
What the theorem actually says, then, is that $A$ and $B$ can only represent the same linear transformation, each of them with respect to some basis, if they are similar matrices. That is, if $A$ and $B$ are not similar, then there is no way we can pick our bases so that $A$ represents the same linear transformation with respect to the first basis as the transformation that $B$ represents with respect to the second basis. Conversely, if $A$ and $B$ are similar matrices, then we can always find a pair of bases $\beta_1$ and $\beta_2$ such that $A$ represents the same transformation with respect to $\beta_1$ as $B$ represents with respect to $\beta_2$.
Part II Change of Basis
To see why this works requires understanding the concept of change of basis. That is, we need to understand how the matrix that represents a particular transformation changes as we change the basis with respect to which we want to express that linear transformation. So, given some transformation $T$ which is represented by the matrix $T_1$ with respect to a basis $\beta_1$, and given some other basis $\beta_2$ which we would like to express $T$ with respect to, how can we find the matrix that does so? To do this we have to construct the change of basis matrix.
Let's say that the matrix that expresses $T$ relative to $\beta_2$ is $T_2$. Given some vector $v \in V$ expressed with respect to $\beta_2$ as a column vector, we expect that when we multiply the matrix $T_2$ by $v$ we get a column vector $T_2v$ that expresses $T(v)$ with respect to $\beta_2$. We should think of the matrix $T_2$ as taking in a vector expressed with respect to $\beta_2$ and spitting out what the transformation $T$ does to that vector, expressed with respect to $\beta_2$.
What we have so far is a way of taking in a vector expressed with respect to $\beta_1$, and spitting out what the transformation does to that vector expressed with respect to $\beta_1$. This is given by the matrix $T_1$. So what we need is some way of taking a vector expressed with respect to $\beta_2$, and finding out how to express it with respect to $\beta_1$. That way, we can feed in that vector expressed with respect to $\beta_1$ to our matrix $T_1$, which will then dutifully spit out what $T$ does to that vector expressed with respect to $\beta_1$, when we multiply $T_1$ by that vector. Since the output is now expressed with respect to $\beta_1$, we also need some way of taking that output and expressing it with respect to $\beta_2$, which will then complete the process.
Let's have $\beta_1 = \{e_1,\ldots,e_n\}$ and $\beta_2 = \{f_1,\ldots f_n\}$. When we write down a vector $v$ with respect to $\beta_2$, what we have is $v = v_1f_1 + v_2f_2 + \cdots v_nf_n$, where the $v_i$'s are the coefficients of $v$ with respect to $\beta_2$. Therefore, if we could just write down the vectors of $\beta_2$ with respect to $\beta_1$, we could then add up that entire linear combination to find out what $v$ looks like with respect to $\beta_1$. That is, we want $f_1 = f_{11}e_1 + f_{21}e_2 + \cdots + f_{n1}e_n$ so that the $f_{i1}$'s are the coefficients of $f_1$ with respect to $\beta_1$. Similarly, we want $f_2 = f_{12}e_1 + f_{22}e_2 + \cdots + f_{n2}e_n$ so that the $f_{2i}$'s are the coefficients of $f_2$ with respect to $\beta_1$. Proceeding onward, we want $f_j = f_{1j}e_1 + f_{2j}e_2 + \cdots + f_{nj}e_n$ for $1 \le j \le n$, so that the $f_{ij}$'s are the coefficients of $f_j$ with respect to $\beta_1$. Then we find that
$$\begin{aligned}
v = v_1f_1 + v_2f_2 + \cdots v_nf_n = \hspace{1mm}&v_1(f_{11}e_1 + f_{21}e_2 + \cdots + f_{n1}e_n) \hspace{1mm} + \\
&v_2(f_{12}e_1 + f_{22}e_2 + \cdots + f_{n2}e_n) \hspace{1mm} + \\
&\hspace{2cm} \vdots \\
&v_n(f_{1n}e_1 + f_{2n}e_2 + \cdots + f_{nn}e_n) \\
= \hspace{1mm} &\hspace{4mm} (v_1f_{11} + v_2f_{12} + \cdots + v_nf_{1n})e_1 \hspace{1mm} + \\
&\hspace{4mm} (v_1f_{21} + v_2f_{22} + \cdots + v_nf_{2n})e_2 \hspace{1mm} + \\
&\hspace{2cm} \vdots \\
&\hspace{4mm} (v_1f_{n1} + v_2f_{n2} + \cdots + v_nf_{nn})e_n
\end{aligned}$$
This looks exactly like matrix multiplication. This inspires us to package together all those $f_{ij}$'s into a single matrix $M = [f_{ij}]$, and observe that we can express $v$ as a column vector with respect to $\beta_1$ like so:
$$v = \begin{bmatrix}
f_{11} & f_{12} & \cdots & f_{1n} \\
f_{21} & f_{22} & \cdots & f_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
f_{n1} & f_{n2} & \cdots & f_{nn}
\end{bmatrix}
\begin{bmatrix}
v_1 \\ v_2 \\ \vdots \\ v_n
\end{bmatrix}$$
where the $v_i$'s are again the components of $v$ with respect to $\beta_2$.
So we've got exactly what we wanted - we have a matrix $M$ that when we muliply it by any vector expressed with respect to $\beta_2$, we get the same vector expressed with respect to $\beta_1$. The matrix $M$ that we just constructed is called the change of coordinates matrix, since it changes the coordinates with respect to which the vector is expressed. Now we need a way of going in the opposite direction - that is, taking a vector expressed with respect to $\beta_1$ and expressing it in terms of $\beta_2$. The matrix that will do this for us is $M^{-1}$. Can you see why? It is precisely the matrix that "undoes" the action that $M$ does, so it has to be the inverse matrix of $M$. Perhaps a bit counterintuitively, the matrix $M^{-1}$ is called the change of basis matrix. This will give us everything we need. The matrix that expresses $T$ with respect to $\beta_2$ is as follows:
$$T_2 = M^{-1}T_1M$$
Again, do you see why? When you multiply $T_2$ by a vector expressed with respect to $\beta_2$, first it gets multiplied by $M$, so that it is now expressed with respect to $\beta_1$. The matrix $T_1$ then takes this vector and gives you what $T$ does to it expressed in terms of $\beta_1$, and then the matrix $M^{-1}$ then takes this vector and expresses it back in terms of $\beta_2$, thus completing the process.
Part III Wrapping It Up
Now that we know how to express a linear transformation with respect to arbitrary bases, it should really seem quite obvious why similarity is necessary for two matrices two represent the same transformation, and you have mentioned that that part seems to make sense to you. It's essentially baked into the process! What about the other direction? Well, if we can find a matrix $M$ such that $B = M^{-1}AM$, then we can think of $M$ as being the change of coordinates matrix. That is, we think of $M$ as taking vectors expressed with respect to the basis we are using for $B$, and expressing them with respect to a new basis with respect to which $A$ represents the same transformation. So any two matrices that are similar can represent the same linear transformation if you pick the right bases.