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$.