Why are matrices indexed by row first? I am wondering is there some greater thought behind indexing matrices in form (row, column), or is it just something that someone did, and everybody else followed?
When I'm looking at the matrix, I find it easiest to imagine it as numbers laid out in 2D grid. From my previous education I usually follow (x,y) order, and it seems like in many other areas we usually deal with x before y. When I'm thinking ${A_{3 1}}$, I'd think x = 3, y = 1, and therefore get 3rd column and 1st row. This would be wrong - I need to do otherwise(y's first).
Why so?

I don't know the historical reason, but this is how I understand it intuitively based on how vectors and matrices are used in modern mathematics and computer graphics.
Vectors are most commonly notated in column major (vertical) form:
$$
\begin{bmatrix}
x \\
y \\
z \\
\end{bmatrix}
$$
When looking up matrix transformations for example, the overwhelming majority you find will be given using column vectors. For example, from wikipedia:
$$
\begin{bmatrix}
  x' \\
  y' \\
\end{bmatrix} = \begin{bmatrix}
  \cos\theta & -\sin\theta \\
  \sin\theta &  \cos\theta \\
\end{bmatrix}\begin{bmatrix}
  x \\
  y \\
\end{bmatrix}
$$
Since vectors are thought of as columns, it makes sense that you can just consider a matrix to be multiple column vectors together:
$$ \require{color}
\begin{bmatrix}
\colorbox{lightgreen}{$x_1$} & \colorbox{lightblue}{$x_2$} & \colorbox{yellow}{$x_3$} \\
\colorbox{lightgreen}{$y_1$} & \colorbox{lightblue}{$y_2$} & \colorbox{yellow}{$y_3$} \\
\colorbox{lightgreen}{$z_1$} & \colorbox{lightblue}{$z_2$} & \colorbox{yellow}{$z_3$} \\
\end{bmatrix}
$$
In this way, the notation of M-by-N or Row-by-Column makes perfect sense. The dimensionality of the vectors (i.e 2D, 3D) is most important, the number of vectors is in the matrix is of secondary importance.
To illustrate:
$$ \require{color}
\begin{bmatrix}
\colorbox{lightgreen}{$x_1$} & \colorbox{lightblue}{$x_2$} & \colorbox{yellow}{$x_3$} \\
\colorbox{lightgreen}{$y_1$} & \colorbox{lightblue}{$y_2$} & \colorbox{yellow}{$y_3$} \\
\end{bmatrix}
$$
These are 2D vectors and we have 3 of them, therefore this is a $2 \times 3$ matrix.
$$ \require{color}
\begin{bmatrix}
\colorbox{lightgreen}{$x_1$} & \colorbox{lightblue}{$x_2$} & \colorbox{yellow}{$x_3$} & \colorbox{orange}{$x_4$} & \colorbox{pink}{$x_5$} \\
\colorbox{lightgreen}{$y_1$} & \colorbox{lightblue}{$y_2$} & \colorbox{yellow}{$y_3$} & \colorbox{orange}{$y_4$} & \colorbox{pink}{$y_5$} \\
\colorbox{lightgreen}{$z_1$} & \colorbox{lightblue}{$z_2$} & \colorbox{yellow}{$z_3$} & \colorbox{orange}{$z_4$} & \colorbox{pink}{$z_5$} \\
\end{bmatrix}
$$
These are 3D vectors and we have 5 of them, therefore this is a $3 \times 5$ matrix.
