What does the vector space of $M_{m \times n}$ really mean? Is it both the row space and the column space of $M$ together?
If I only look at the column space, I would say that a basis for the columspace would be a $1\times n$ matrix (assuming $n$ linearly independent column vectors). Similarly a basis for the row space would be $m\times 1$ matrix. Is this right? How do I find the basis for the $m\times n$ matrix?
It means the collection of all $n \times m$ matrices. This set equipped with the sum and multiplication by scalar is a vector space. Then comes the question of how one can characterize an element in $M_{m \times n}$. To do this you will need to find a basis of $M_{m \times n}$, a set of independet matrices in $M_{m \times n}$ that generate $M_{m \times n}$. In this way if one gives you a set of numbers (coordinates with respect to that basis) you can build from that the corresponding matrix in $M_{m \times n}$. Intuitively since an $m \times n$ matrix will have $mn$ entries you will need $mn$ numbers that will be the coefficents of a linear combination of the elements of your basis. A basis of $M_{m \times n}$ is commonly the set of all matrices with only one element set to $1$ and everything else set to $0$. For example $\begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix} = 1\begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix} + 2 \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} + 3 \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} + 4 \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix} $
The column (row) space of a matrix is a different thing, it's the set of all the linear combinations of the columns (rows) of your matrix.