An algorithm to compute the steady state probability vector for the matrix analogues of Markov chains of the M/G/1 type is presented. It is a stable recursive scheme involving only nonnegative quantities. An essential constituent of the computational scheme is the minimal nonnegative solution of a nonlinear matrix equation. For the computation of the starting vector of the recursive scheme a method originally developed in the context of Markov renewal branching processes is recommended.