Two new implementations of the EM algorithm are proposed for maximum likelihood fitting of generalized linear mixed models. Both methods utilize random (independent and identically distributed) sampling to construct Monte Carlo approximations at the E-step. One approach involves generating random samples from the exact conditional distribution of the random effects (given the data) by rejection sampling, using the marginal distribution as a candidate. The second method uses a multivariate-t importance sampling approximation. In many applications the two methods are complementary. Rejection sampling is more efficient when sample sizes are small, while importance sampling is better with larger sample sizes. Monte Carlo approximation using random samples allows the Monte Carlo error at each iteration to be assessed using standard central limit theory combined with Taylor series methods. Specifically, we construct a sandwich variance estimate for the maximizer at each approximate E-step. This suggests a rule for automatically increasing the Monte Carlo sample size after iterations in which the true EM step is swamped by Monte Carlo error. In contrast, techniques for assessing Monte Carlo error have not been developed for use with alternative implementations of Monte Carlo EM utilizing Markov chain Monte Carlo E-step approximations. Three different data sets, including the infamous salamander data of McCullagh and Nelder (1989, Chapter 14), are used to illustrate the techniques and to compare them with the alternatives. The results show that the proposed methods can be considerably more efficient than those based on Markov chain Monte Carlo. On the other hand, the proposed methods may break down when the intractable integrals in the likelihood function are of high dimension.