We investigate three new strategies for the numerical solution of optimal stopping problems within the Regression Monte Carlo (RMC) framework of Longstaff and Schwartz. First, we propose the use of stochastic kriging (Gaussian process) meta-models for fitting the continuation value. Kriging offers a flexible, nonparametric regression approach that quantifies approximation quality. Second, we connect the choice of stochastic grids used in RMC to the Design of Experiments paradigm. We examine space-filling and adaptive experimental designs; we also investigate the use of batching with replicated simulations at design sites to improve the signal-to-noise ratio. Third, we explore classification models for directly approximating the exercise region. Numerical case studies for valuing Bermudan Puts and Max-Calls under a variety of asset dynamics illustrate that our methods offer significant reduction in simulation budgets over existing approaches.