Multicellularity has arisen independently several times, but most famously twice, in the two lineages giving rise to plants and animals. In fact, the last unicellular ancestors of these two lineages were not particularly closely related, and the last common ancestor of both plants and animals also gave rise to an enormous number of extant unicellular progeny, including all of the fungi. When I began serious work on the regulation of pre-mRNA splicing in plants in 2001 I did so with an awareness of how very similar the process is to pre-mRNA splicing in animals. This is all the more striking because so many species have lost this complexity. In fact, plants and animals share many processes that must have been present in the last common ancestor, but have been lost in many unicellular eukaryotes derived from that same ancestory. RNA figures heavily in the list, which includes microRNAs, U12 introns, the exon junction complex and complex alternative splicing.
Although the last common ancestor of plants and animals was almost certainly much more complex than most modern unicellular eukaryotes (at least in terms of its genome), it was probably not multicellular. The signals that control development in animals (wnts, hedgehog, FGFs, TGF-betas, etc.) are completely missing in plants. Likewise, the genes involved in meristem maintenance, ethylene-signaling, auxin-signaling and so on are missing in animals. It's also worth pointing out that the opisthokont clade (which includes animals and the fungi) is well-established (see the figure, which is from the Tree of Life Web Project).
Perhaps most convincing are the exceptions: the processes shared by animals and plants but missing from most unicellular eukaryotes are not missing from all. U12 introns were recently found in distantly related protists and in a fungus (see my comment). MicroRNAs were recently described in Chlamydomonas reinhardtii, a unicellular green alga (Zhao et al., 2007). There is even a miRNA family that is appears to be conserved between plants and animals and targets a homologous family of splicing regulators (Arteaga-Vazquez et al. 2006).
It is therefore frustrating to read commentaries that are written as though genomic complexity is new. For example, Ram and Ast (2007) mistakenly generalize from S. cerevisiae to S. pombe (which retains more genomic complexity of several sorts, including alternative splicing) and talk about "before and after" incorrectly. Their conclusion, that "SR proteins had already facilitated the splicing of weak introns before the evolution of alternative splicing" may be correct, but complex alternative splicing was almost certainly present in the last common ancestor of plants and animals. I say this based on the fact that it had many genes whose products function in the regulation of alternative splicing, and which have been lost in unicellular descendants lacking complex alternative splicing (among these is a repertoire of at least four SR proteins).
What is most interesting to me is the correlation between developmental complexity and retention of genomic complexity, including alternative splicing and miRNAs. It might not have evolved with multicellularity, but the ancient RNA toolkit might be very useful when it comes to building a complex organism.