Rows and columns only exist in your mind.
They don't exist in math
row-major and column-major is completely irrelevant, until you want to implement multi-dimensional arrays

That's just the computer science side of row/column majorness.
The same issue does exist in math:

So, Mathematically, a row major matrix would be:

Xx Xy Xz 0
Yx Yy Yz 0
Zx Zy Zz 0
Tx Ty Tz 1

And a column major matrix would be:

Xx Yx Zx Tx
Xy Yy Zy Ty
Xz Yz Zz Tz
0  0  0  1

With X, Y, Z being the basis vectors and T being a transform component.

Those are two different ways of organizing data within a matrix on paper, in pure maths. The basis vectors are either in the rows of the matrix or the coumns. This does change the way that your math works out! Depending on which one you choose, you'll either be treating positions as "row-vectors" or "column-vectors", i.e. a vertex position, called (Vx, Vy, Vz) will either be a 1x4 matrix:
$$\begin{bmatrix} Vx & Vy & Vz & 1 \end{bmatrix}$$
or a 4x1 matrix:
$$\begin{bmatrix} Vx\\ Vy\\ Vz\\ 1 \end{bmatrix}$$
This in turn changes whether you'll write posVertex * matWorld * matView * matProj, or matProj * matView * matWorld * posVertex -- a 1x4 must be on the left of a 4x4, and a 4x1 must be on the right of a 4x4:
$$\begin{matrix} Xx & Yx & Zx & Tx \\ Xy & Yy & Zy & Ty \\ Xz & Yz & Zz & Tz \\ 0 & 0 & 0 & 1 \\ \end{matrix} \begin{bmatrix} Vx\\ Vy\\ Vz\\ 1 \end{bmatrix} $$

$$\begin{bmatrix} Vx & Vy & Vz & 1 \end{bmatrix} \begin{matrix} Xx & Xy & Xz & 0 \\ Yx & Yy & Yz & 0 \\ Zx & Zy & Zz & 0 \\ Tx & Ty & Tz & 1 \\ \end{matrix}$$
so majorness is an issue in your math, and also a completely different issue in more-than-one-dimensional-array based code.

Traditionally, mathematicians will use column-vectors just because, but some will use row-vectors, so some text-books differ from others when teaching matrices -- the theory in some might be completely backwards to others! Traditionally, GL and D3D tutorials typically taught matrix math completely opposite to each other, leading to a lot of confusion.
In computer graphics, a lot of older material uses row-vectors even though they were unpopular -- one reason was that Jim Blinn (of Blinn-Phong fame) found that row-vector math was easier to write on a typewriter... causing many of his students to learn this less popular mathematical convention

This gets confusing because a lot of the time when people have problems with matrix code, people don't specify whether they're talking about the mathematical concept, or the computer science concept... Also, you can often make two mistakes and still have your code work fine, because if you get either of these conventions wrong, it's the same effect as if you'd transposed your 4x4 matrix... so if you get your math convention wrong and your comp-sci convention wrong, then you transpose your data twice, which ends up cancelling out! Because of this, often you can use 3rd party libraries that use opposite conventions to the rest of your code, yet they still happen to work just fine

e.g. the D3DX matrix library used row-major maths, and row-major arrays, but HLSL by default uses column-major arrays. This meant that if you wanted to use row-major maths in your HLSL code, you would have to transpose the data when sending it from D3DX to HLSL. Alternatively, some people simply used column-major maths in their shaders and skipped the transpose (which IMHO is a fireable offense! )

In that case, mathematically is subscript Mij always interpreted as the i-th column and j-th row of Matrix M?
Regardless of the major of the matrix?

It is very common to see [row][column] instead of [column][row] indexing

Yes mathematicians tend to write [row][column], whereas programmers tend to write [x][y], which would be [column][row]... In the case of matrix code, I would break ranks with programming tradition and adopt the popular mathematical convention -- the first coordinate is the row. e.g. above, when I mention a 4x1 matrix, it has 4 rows and 1 column, or in other words, width=1, height=4

@Hodgman

That makes a lot of sense. What you are saying is that matematically if we lay out the elements like so:

00 01 02
10 11 12
20 21 22

That indexing scheme is it! Both Row & Column major matrices will be laid out in that scheme.

The only difference is, in row major the X basis occupies elements 00, 01 and 02

And in a column major matrix the X basis will occupy elements 00, 10 and 20

^ Is this latest revelation the correct one? I feel like i finally got it!

The actual subscripts & layout are independent of the "major" of the matrix.

The major just adds meaning to an already defined / laid out grid of numbers!

Yes, those are the typical names for each element.

Just beware that every convention is violated occasionally! When using a new library/middleware, always try to check their documentation to make sure they're using the common conventions.

In maths row-major, row #0 contains X: 00, 01, 02 == Xx, Xy, Xz

In maths column-major, column #0 contains X: 00, 10, 20 == Xx, Xy, Xz

In comp-sci row-major, rows are stored contiguously, so that matrix is stored as: 00, 01, 02, 10, 11, 12, 20, 21, 22

In comp-sci column-major, columns are stored contiguously, so that matrix is stored as: 00, 10, 20, 01, 11, 21, 02, 12, 22