We extend the stochastic block model to include per-node (non-graphical) side information, generalizing past works involving noisy observation of the node labels. In cases where exact recovery of node labels is not achieved by observing the graph, a necessary and sufficient condition is obtained on the required asymptotic quality of noisy-label side information to induce exact recovery. We then analyze belief propagation in the stochastic block model in the presence of side information, obtaining an expression for residual errors under M-ary side information that generalizes and recovers the results of Mossel and Xu for binary noisy observations. We calculate the EXIT equations for this problem, and demonstrate with a few examples.