Systems and methods for treating spinal stenosis insert a guide element percutaneously into proximity with the adjacent spinous processes. The systems and methods direct an implant device over the guide element to a position resting between the adjacent spinous processes. The device is sized and configured to distend the adjacent spinous processes. The implant device itself can be variously constructed. It can, e.g., possess threaded lands and/or a notched region in which a spinous process can rest. The implant device has a lumen to accommodate passage of the guide element, so that the device can be passed percutaneously over the guide element for implantation between adjacent spinous processes.