It seems to be remarkably easy for eukaryotes, with their excessive number of genes (probably accumulated via drift and non-adaptive processes) which can be co-opted for cell-to-cell communication. There are those that argue that prokaryotes are too heavily optimized for efficient fast reproduction to make huge multicellular complexes- though it turns out that they actually do specialize themselves a bit when they are growing in colonies or biofilms to provide for the colony as a whole.