Take the standard basis of the vector space, which consists of the matrices $E_{ij}$ with $1\leq i,j\leq N$; $E_{ij}$ has a $1$ in the $(i,j)$th entry, and $0$ elsewhere.
What does $T$ do to the basis vectors? $T(E_{ij}) = AE_{ij}$. What is $AE_{ij}$? It is a matrix that has $0$s everwhere, except in the $j$th column; the $j$th column of $AE_{ij}$ is the $i$th column of $A$. That is:
$$T(E_{ij}) = a_{1i}E_{1j} + a_{2i}E_{2j} + \cdots + a_{Ni}E_{Nj}$$
where $a_{rs}$ is the $(r,s)$th entry of $A$.
Note that the image of $E_{ij}$ can be expressed using the matrices with the same column entry, $E_{1j}, E_{2j},\ldots,E_{Nj}$, and only those matrices.
Added. This suggests that instead of taking the
usual ordered basis, which takes the $E_{ij}$ ordered by rows,
$$E_{11},E_{12},E_{13},\ldots,E_{1N},E_{21},E_{22},\ldots,E_{NN},$$
things will be easier if we take the basis ordering the matrices by
columns:
$$\beta=[E_{11}, E_{21}, E_{31},\ldots,E_{N1},E_{12},E_{22},\ldots,E_{NN}.$$
The reason is that when we compute $T(E_{ij})$, if the basis is ordered "by rows", then the coordinate vector is going to have nonzero entries splattered all around haphazardly; but if we have the basis ordered by "columns", then the nonzero entries will all be together. More: the image of $E_{11}$ will only involve the first $N$ vectors of the basis, the image of $E_{21}$ will also involve only the first $N$ vectors of the basis, and so on; generally, the image of $E_{ij}$ will involve only the $(i-1)N+1$st through $iN$th vectors in the basis. Thus, the coordinate matrix will be
block-diagonal: the first $N$ vectors in the basis will have images that only use the first $N$. The second $N$ vectors, from the $N+1$st through the $2N$th, will only the same vectors; and so on. So we will have a nice matrix of the form
$$\left(\begin{array}{cccc}
B_1 & \mathbf{0} & \cdots & \mathbf{0}\\
\mathbf{0} & B_2 & \cdots & \mathbf{0}\\
\vdots & \vdots & \ddots & \vdots\\
\mathbf{0} & \mathbf{0} & \cdots & B_N
\end{array}\right)$$
where $B_i$ is an $N\times N$ matrix; block diagonal matrices are much simpler to handle than just regular matrices, so this is the way to go here.
So what is the matrix of $T$ relative to this basis? Well, $T(E_{11})$ is a matrix that has the first column of $A$ as the first column, the rest $0$s. So the first column of $[T]$ is
$$\left(\begin{array}{c}a_{11}\\a_{21}\\\vdots\\ a_{N1}\\0\\0\\\vdots\\0\end{array}\right).$$
What is $T(E_{21})$? It is a matrix that has $0$s everywhere, except that the first column is the second column of $A$. So the second column of $[T]$ is
$$\left(\begin{array}{c}a_{21}\\a_{22}\\\vdots\\ a_{N1}\\0\\0\\\vdots\\0\end{array}\right).$$
And so on.
So, when you are done with the first $N$ columns of $[T]$, what happens? You get a block on the upper left corner of $[T]$, which is exactly equal to $A$. That is, the matrix looks like
$$[T] = \left(\begin{array}{ccc}
A & \cdots & *\\
0 & \cdots & *\\
\vdots & \ddots & \vdots \\
0 & * & *
\end{array}\right),$$
where "$0$" stands for an appropriately size $0$ matrix, and $*$ stands for a as-yet-unknown matrix.
Continue this way. You will find that $[T]$ has a very special form, which makes computing the characteristic and minimal polynomials very easy. It will also show why if $A$ is diagonalizable, so is $T$, and exactly by what vectors.
Added Example. Take the example you give in comments, $N=2$, and
$$A = \left(\begin{array}{cc}
1& 0\\
0 & 2
\end{array}\right).$$
The basis for the space of $2\times 2$ matrices that I suggest is, in order, $E_{11}$, $E_{21}$, $E_{12}$, and $E_{22}$, that is:
$$E_{11} = \left(\begin{array}{cc}
1 & 0 \\ 0 & 0\end{array}\right),\quad E_{21}=\left(\begin{array}{cc}0&0\\1& 0\end{array}\right),\quad E_{12}=\left(\begin{array}{cc}0 &1\\0 &0\end{array}\right),\quad E_{22}=\left(\begin{array}{cc}0&0\\0&1
\end{array}\right).$$
Now, we compute what $T$ does to this basis:
$$\begin{align*}
T(E_{11}) &= AE_{11} =\left(\begin{array}{cc}1&0\\0&2\end{array}\right) \left(\begin{array}{cc}1&0\\0&0
\end{array}\right)= \left(\begin{array}{cc}
1 & 0\\0 & 0\end{array}\right)\\
&= 1E_{11} + 0E_{21} + 0E_{12} + 0E_{22}.\\
T(E_{21}) &= AE_{21} =\left(\begin{array}{cc}
1 & 0\\0&2\end{array}\right)\left(\begin{array}{cc}0&0\\1&0
\end{array}\right)= \left(\begin{array}{cc}
0 & 0\\
2 & 0
\end{array}\right)\\
&= 0E_{11} + 2E_{21} + 0E_{12} + 0E_{22}.\\
T(E_{12}) &= AE_{12} =\left(\begin{array}{cc}
1 & 0\\0&2\end{array}\right)\left(\begin{array}{cc}0&1\\0&0
\end{array}\right)= \left(\begin{array}{cc}
0 & 1\\
0 & 0
\end{array}\right)\\
&= 0E_{11} + 0E_{21} + 1E_{12} + 0E_{22}.\\
T(E_{22}) &= AE_{22} =\left(\begin{array}{cc}
1 & 0\\0&2\end{array}\right)\left(\begin{array}{cc}0&0\\0&1
\end{array}\right) = \left(\begin{array}{cc}
0 & 0\\
0 & 2
\end{array}\right)\\
&= 0E_{11} + 0E_{21} + 0E_{12} + 2E_{22}.
\end{align*}$$
So the coordinate vectors of the images relative to $\beta=[E_{11},E_{21},E_{12},E_{22}]$ are:
$$\begin{align*}
[T(E_{11})]_{\beta} &=(1,0,0,0)^T\\
[T(E_{21})]_{\beta} &=(0,2,0,0)^T\\
[T(E_{12})]_{\beta} &=(0,0,1,0)^T\\
[T(E_{22})]_{\beta} &=(0,0,0,2)^T.
\end{align*}$$
So the coordinate matrix of $T$ relative to $\beta$ is given by:
$$[T] = \left(\begin{array}{cccc}
1 & 0 & 0 & 0\\
0 & 2 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 2
\end{array}\right) = =\left(\begin{array}{cc|cc}
1 & 0 & 0 & 0\\
0 & 2 & 0 & 0\\
\hline
0 & 0 & 1 & 0\\
0 & 0 & 0 & 2
\end{array}\right) = \left(\begin{array}{cc}
A & \mathbf{0}\\
\mathbf{0} & A
\end{array}\right),$$
that is, a block diagonal matrix with two blocks, each block equal to $A$.
Example 2. Similar, just a bit different so that you don't get confused by the fact that we got a diagonal matrix in this case. Take
and
$$A = \left(\begin{array}{cc}
1& 0\\
3 & 2
\end{array}\right).$$
Now, we compute what $T$ does to this basis:
$$\begin{align*}
T(E_{11}) &= AE_{11} =\left(\begin{array}{cc}1&0\\3&2\end{array}\right) \left(\begin{array}{cc}1&0\\0&0
\end{array}\right)= \left(\begin{array}{cc}
1 & 0\\3 & 0\end{array}\right)\\
&= 1E_{11} + 3E_{21} + 0E_{12} + 0E_{22}.\\
T(E_{21}) &= AE_{21} =\left(\begin{array}{cc}
1 & 0\\3&2\end{array}\right)\left(\begin{array}{cc}0&0\\1&0
\end{array}\right)= \left(\begin{array}{cc}
0 & 0\\
2 & 0
\end{array}\right)\\
&= 0E_{11} + 2E_{21} + 0E_{12} + 0E_{22}.\\
T(E_{12}) &= AE_{12} =\left(\begin{array}{cc}
1 & 0\\3&2\end{array}\right)\left(\begin{array}{cc}0&1\\0&0
\end{array}\right)= \left(\begin{array}{cc}
0 & 1\\
0 & 3
\end{array}\right)\\
&= 0E_{11} + 0E_{21} + 1E_{12} + 3E_{22}.\\
T(E_{22}) &= AE_{22} =\left(\begin{array}{cc}
1 & 0\\3&2\end{array}\right)\left(\begin{array}{cc}0&0\\0&1
\end{array}\right) = \left(\begin{array}{cc}
0 & 0\\
0 & 2
\end{array}\right)\\
&= 0E_{11} + 0E_{21} + 0E_{12} + 2E_{22}.
\end{align*}$$
So the coordinate vectors of the images relative to $\beta=[E_{11},E_{21},E_{12},E_{22}]$ are:
$$\begin{align*}
[T(E_{11})]_{\beta} &=(1,3,0,0)^T\\
[T(E_{21})]_{\beta} &=(0,2,0,0)^T\\
[T(E_{12})]_{\beta} &=(0,0,1,3)^T\\
[T(E_{22})]_{\beta} &=(0,0,0,2)^T.
\end{align*}$$
So the coordinate matrix of $T$ relative to $\beta$ is given by:
$$[T] = \left(\begin{array}{cccc}
1 & 0 & 0 & 0\\
3 & 2 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 3 & 2
\end{array}\right) = =\left(\begin{array}{cc|cc}
1 & 0 & 0 & 0\\
3 & 2 & 0 & 0\\
\hline
0 & 0 & 1 & 0\\
0 & 0 & 3 & 2
\end{array}\right) = \left(\begin{array}{cc}
A & \mathbf{0}\\
\mathbf{0} & A
\end{array}\right),$$
once again, a block diagonal matrix with two blocks, each block equal to $A$.