Unsure of syntax used in Searchable Encryption This image is taken from Algorithm 1 from "Σoφoς – Forward Secure Searchable Encryption, CCS '16".

On line 4 there seems to be a new variable, M, that is never defined throughout the rest of the paper. Should I attain a random byte[] and set that as the value of ST_0? 

This is being implemented on a Java programme.
$\mathcal{M}$ is the domain of the inverse trapdoor permutation $\pi^{-1}$. For example, if $\pi^{-1}(m)= m^d \bmod N$ implemented using RSA, then $\mathcal{M}=Z^*_N$. The domain/range of $\pi$ and $\pi^{-1}$ are all $\mathcal{M}=Z^*_N$. 

Generate a random big integer in $Z^*_N$ (roughly from range 1 to $N$) should be fine (there is a negligible probability of getting something not in $Z^*_N$, but since it is negligible we don't care).