The authors indicate the blueprints were already present but the multicellular expression stopped being optional in their evolved population:
The ability of wild-type C. reinhardtii to form palmelloids suggests that the founding population in our experiment already possessed a toolkit for producing multicellular structures. However, while the palmelloid condition is expressed facultatively in wild-type C. reinhardtii, the strains that evolved in our experiment are obligately multicellular.
Maybe I'm not familiar with how this term is used in biology but given the above it seems the "de novo" claim in the paper title is a little sensationalist.