Sampling-based motion planning techniques have emerged as an efficient algorithmic paradigm for solving complex motion planning problems. These approaches use a set of probing samples to construct an implicit topological graph of the robot's state space, allowing arbitrarily accurate representations as the number of samples increases to infinity. In practice, however, solution trajectories only rely on few critical states, often defined by structure in the state space (e.g., doorways). In this work we propose a general method to learn to identify these critical states via graph-theoretic techniques and to use them within a hierarchical graph, termed Critical Probabilistic Roadmaps. Critical PRMs are demonstrated to achieve two orders of magnitude improvement over uniform sampling, while perserving the theoretical guarantees of sampling-based motion planning.