Many Monte Carlo photon transport codes draw samples of the scattering cosine, and corresponding energy loss, for Compton scatter from the Klein-Nishina differential scattering cross section. We present new schemes for sampling by rejection that offer advantages in run time, parsimony in use of random numbers, and/or acceptance efficiency. These are compared with Kahn's method, which was recommended by Lux and Koblinger in 1991. We conclude with recommendations for both algorithmic and table-based approaches.