Trends show that machine-to-machine (M2M) devices are going to grow by orders of magnitude, far surpassing the number of mobile devices. This unprecedented scale and the fact that M2M traffic typically consists of many small-sized transmissions make the data and signaling overhead of introducing M2M traffic into cellular networks a big concern. Fortunately, it is possible to exploit certain unique characteristics of M2M traffic, like periodicity and delay tolerance in its scheduling, to alleviate these concerns. In this paper, we propose SERA - a two-level Scheduled Randomization framework, which does precisely this, and efficiently integrates M2M traffic into cellular networks. Broadly, SERA consists of (i) a central controller that defines certain coarse-level transmission parameters to govern M2M traffic in the next scheduling period and (ii) a simple distributed randomized algorithm at each M2M device that governs fine-grained transmission decisions within the period. Using experiments and analyses, we show that compared to existing techniques for M2M traffic management, SERA can lower peak traffic load by 30-40%, bring down the total time spent under congestion by 30-40%, and that these gains are robust to errors in traffic prediction.