SpaceX's demonstrated booster-landing ability isn't the result of a breakthrough but rather a bunch of small incremental improvements. The major limitation has been funding and the will to make it happen.
In 1966, unmanned spacecraft landed on the Moon under rocket power in the Surveyor program. It used (IIRC) three fixed-position thrusters, pulsed, to control its attitude and rate of descent. This was a relatively small spacecraft (about 3m tall and massing 300kg), which makes things easier; its landing legs were wide so it could remain stable if it touched down at the wrong attitude. Under the moon's lower gravity, response times are somewhat less critical, so it can be thought of as "easy mode" for autonomous rocket landings. However, it proves that a basic radar altimeter, an inertial platform to determine the spacecraft's attitude, and a simple control loop are sufficient to land with.
In the Apollo program, the LM descent stage was only a little more sophisticated; a throttleable engine on a gimbal mount was used to control direction and rate of descent, and smaller thrusters used to control attitude. The human pilot could, in principle, designate a landing point and then let the computer do the rest of the flying all the way to touchdown, but in practice every Apollo commander took control in a semi-manual mode at around 150m altitude, controlling the ship's attitude and rate of descent. The major limitation at this point was that the autonomous system had no way of knowing if it was coming down on flat ground or on a pile of boulders; the radar altimeter was a single low resolution probe.
Landing a rocket on Earth, under six times higher gravity, requires faster control response: not necessarily a much faster computer (you can manage with only a few thousand operations per second; the equations are not that complex), but things like fast and precise throttle valves. I don't know much about the history there, but I imagine this kind of thing was available in the 1960s as well. On the up side, when landing on Earth, it's much easier to arrange for a large flat area to land on!
As @Dragongeek mentions, the USSR flew the Buran space shuttle in 1988; its only flight was an unmanned launch to orbit and return to Earth. It landed in winged, horizontal flight, so it's not directly comparable to Falcon 9, although the guidance and control problems are similar in complexity.
In 1993, the DC-X project demonstrated rocket-powered, autonomous, vertical landing of a 12-meter tall vehicle from 3km altitude. DC-X had some problems, to be sure, and was eventually canceled for lack of funding, but there weren't any breakthroughs that needed to be made. Like Falcon 9, DC-X used multiple, gimbaled, deep-throttling engines as its primary flight control, augmented with aerodynamic surfaces and attitude-control thrusters, and used GPS in its guidance and control system.
GPS has been a big help to precision landings, of course; the Falcon first stage knows its own location via GPS and guides itself towards a specified point in absolute space -- the center of a landing pad or ASDS. Without GPS, which was first deployed in the late 1980s, it would be possible to place a radio beacon at the landing point and home in on that.
Arguably, the key to SpaceX's success has been that a failed reusable launcher can still be a successful expendable launcher. By making a commercial orbital launcher that is practical to fly in the expendable mode, and experimenting with landings on the payload customer's dime, they've substantially offset the costs of landing R&D.
Modern computer vision algorithms would make it possible to find and target a flat landing site on another planet or moon, which SpaceX may have to do for their first Moon or Mars landings. This technology is a more recent development. It requires fairly modern amounts of computing power to derive a terrain map from camera views in real time, but that isn't required for what SpaceX is doing today.
