Necessary and sufficient conditions for a matrix to be a valid correlation matrix. It's not too hard to see that any correlation matrix must have certain properties, such as all entries in the range -1 to 1, symmetric, positive semi-definite (excluding pathological cases like singular matrices for the moment).
But I'm wondering about the other direction. If I write down some matrix that is positive semi-definite, is symmetric, has 1's along the main diagonal, and all entries are between -1 and 1, does this guarantee that there exists a set of random variables giving rise to that correlation matrix?
If the answer is easy to see, a helpful hint about how to define the set of random variables that would give rise to a given matrix would be appreciated.

Yes, although the restriction that all entries are between $-1$ and $1$ is implied by the other properties (and so is not needed).
Let $\Sigma$ be a $n \times n$, symmetric, positive semidefinite matrix with $1$'s along the main diagonal.
First, $\Sigma$ is a covariance matrix.  Since $\Sigma$ is symmetric and positive semidefinite, $\Sigma$ has a nonnegative symmetric square root $\Sigma^{1/2}$.  Let $X$ be a $n$-vector of independent random variables, each with variance $1$.  (For example, $X$ could be an $n$-vector of independent $N(0,1)$ random variables.)  Construct the $n$-vector $\Sigma^{1/2} X$.  Then, by properties of covariance matrices, $$\text{cov} (\Sigma^{1/2} X) = \Sigma^{1/2} \text{cov}(X) \Sigma^{1/2} = \Sigma^{1/2} I \Sigma^{1/2} = \Sigma.$$  Thus $\Sigma$ is the covariance matrix for the random vector $\Sigma^{1/2} X$. (This derivation is on the Wikipedia article for covariance matrices.)
Second, since $\Sigma$ has $1$'s on its diagonal, the standard deviation of each random variable in $\Sigma^{1/2} X$ is $1$.  Thus the correlation matrix $R$ for the random vector $\Sigma^{1/2} X$ is $$R = I^{-1} \Sigma I^{-1} = \Sigma.$$  Thus $\Sigma$ is a correlation matrix as well. 
