Long before the first legumes came onto the scene, the early ancestors of Cycads were hard at work fixing atmospheric nitrogen. However, they don't do this on their own. Despite being plentiful in Earth's atmosphere, gaseous nitrogen is not readily available to most forms of life. Only a special subset of organisms are capable of turning gaseous nitrogen into forms usable for life. Some of the first organisms to do this were the cyanobacteria, which has led them down the path towards symbioses with various plants on many occasions.
Cycads are but one branch of the gymnosperm tree. Their lineage arose at some point between the Carboniferous and Permian eras. Throughout their history it would seem that Cycads have done quite well in poor soils. They owe this success to a partnership they struck up with cyanobacteria. Although it is impossible to say when exactly this happened, all extant cycads we know of today maintain this symbiotic relationship with these tiny prokaryotic organisms.
The relationship takes place in Cycad roots. Cycads don't germinate with cyanobacteria in tow. They must acquire them from their immediate environment. To do so, they begin forming specialized structures called precoralloid roots. Unlike other roots that generally grow downwards, these roots grow upwards. They must situate themselves in the upper layer of soil where enough light penetrates for cyanobacteria to photosynthesize.
The cyanobacteria enter into the precoralloid roots through tiny cracks and take up residence. This causes a change in root development. The Cycad then initiates their development into true coralloid roots, which will house the cyanobacteria from that point on. Cycads appear to be in full control of the relationship, dolling out carbohydrates in return for nitrogen depending on the demands of their environment. Coralloid roots can shed and reform throughout the lifetime of the plant. It is quite remarkable to think about how nitrogen-fixing symbiotic relationships between plants and microbes have evolved independently throughout the history of life on this planet.