As I'm lucky enough to have access to that article, I'm going to extract whatever I can find to answer your question.
To begin with, innate immunity must have evolved first - we can see it at almost all stages of evolution. According to Cooper & Herrin, ever since aerobic respiration gave rise to multicellular organisms which in turn needed protection from invasion by single-cell organisms.
They state that around 500 million years ago, the first adaptive immune systems evolved in vertebrates, but do not explain how although they attempt to. Instead, they explain why we are not able to discern at the moment how this evolution came about. The main reason given is that it is unknown when some key cells evolved (namely natural killer cells and dendritic cells) Additionally, mice and humans evolved two different kinds of natural killer cell receptors relatively recently while sharing a common ancestor only quite a long time ago.
Apparently jawed and jawless vertebrates have also evolved two different kinds of adaptive immune systems. They both seem to rely on the same mechanisms but on a different molecular and genetic basis. Cooper & Herrin conclude that at the current level of research, we are not able to determine the evolution of our immune system.
Source: How did our complex immune system evolve?
Personally, if I'm allowed to give in to the temptation of speculation a bit, I would go by a similar strategy as the evolution of Krebs cycle - look which bits make sense even without the rest. I do want to warn that this is purely my fantasy and is made up a bit on the spot :)
I would suppose that natural killer cells may have evolved as the first part, as they seem like they could be of use even without the rest of the adaptive immune system. A cell that can recognise "wrong" cells and induce their apoptosis - very useful in my opinion. This may have lead to innate immune cells presenting antigens. As far as I remember from school (bear with me), the contact with a presenting cell activates killer cells now (?) so this would not be far off. Next B-cells as they have the next practical use in labelling and immobilising pathogens; and finally T-cells as mediators and reinforcers, optimising the system by reducing autoimmunity?
I know, this is quite a pathetic attempt - but I shall trust Cooper & Herrin that a realistic explanation isn't possible at the moment.