You're also confusing the randomness of the steps with the somewhat previsible trend of an entire ecosystem which is evolving. If world is getting warmer and air more dense, you wouldn't be able to guess which mutation occurs but you can predict in time animals would be more adapt to that new ecosystem.
Darwin famously looked at a unusual orchid with a long "tube" leading to nectar, and spoke that "there must be a bird with a long beak here somewhere". He didn't find it at first, but it was discovered later [1]. So you can apply some predictions at how evolution took place if you take a look at the environment. Just as one would guess there must be an immune system in animals if you discover diseases, virus, bacteria etc - or else how would large animals exist?
The adaptive immune system is the one that runs a mini-evolution within your own body as way to counter the extremely rapid rate of evolution in pathogens. There are a few explanations as to how this came about - see my last comment.
Paradoxically, it may be the very success of our immune system which puts selective pressure on pathogens to evolve even faster.
The acquired immune system: a vantage from beneath https://pubmed.ncbi.nlm.nih.gov/15539148/
Could you kindly explain? From the beginning. I’m trying to gain “top-to-bottom” understanding of what we’re discussing.
Also, what was the reason behind placing “immune system” in quotation marks and negating its existence per my reference of it, but delineating it in the format that you did subsequently? I’m trying to figure out where I erred in my choice of words.
Technically, the "immune system" should include anything that prevents pathogenesis (disease).
This would include behavioral things like avoiding people who look sick, and the tendency for sick people to stay indoors as a a population-level adaptation which prevents the spread of microbes.
Neuro-immunology is in fact a burgeoning field and for example we now know that many macrophages in the spleen (typically though to be an immune organ) are in contact with the nervous system, though it's not clear yet what the purpose of this is. Kind of related: some kinds of voluntary meditation can affect the extent of inflammation in the body triggered by bacterial toxins (https://www.pnas.org/doi/10.1073/pnas.1322174111).
If we limit the "immune system" to the parts of the body that directly interacts with microbes, then we still have to split it up into at least two buckets - the innate and the adaptive immune system. The innate immune system recognizes broad categories of molecular patterns which are often found on pathogens (https://en.wikipedia.org/wiki/Pathogen-associated_molecular_...) or of molecules which result from tissue damage (https://en.wikipedia.org/wiki/Damage-associated_molecular_pa...) and reacts very quickly to try to clear the infection/recruit repair molecules.
The innate immune system then recruits the adaptive immune system which takes about 2 weeks. In jawed vertebrates, the adaptive immune system contains a humongous and diverse repertoire of cells which are randomly generated using VDJ recombination (https://en.wikipedia.org/wiki/V(D)J_recombination), and if you are lucky then one of these cells in your body will recognize the pathogen and clone itself to form an army which will clear the disease. A small portion of these clones will then hang around in your body so that the next time you see a similar disease, they are already primed to respond to the infection. This is called immunological memory. The flip-side to this, which many people forget, is immunological tolerance. That means that if the foreign cell you encountered did not cause you any damage, then the next time you see it you will actually react to it even less than the first time. Technically, tolerance is also a form of immunological memory since the second response depends on the first one. Because of this tolerance, "foreignness" is often not enough to induce an immune response other than tolerance, and this is the reason that vaccines require something called an adjuvant, which tricks the immune system into thinking there is danger associated with the foreign body.(https://www.jci.org/articles/view/119978).
Tolerance is critical to keeping around the 'good bacteria' which perform useful functions all over your body such as fermenting fibers into short-chain fatty acids, and taking up niche space so that more greedy bacteria don't invade.
Going back to your question: "How can natural selection account for that?"
The innate immune system can be accounted for in the same way as everything else in biology - variation within populations of individuals selected for individuals which could recognize pathogens. The selective pressure was created by the pathogens themselves.
The adaptive immune system is more complex, since it involves running a mini-evolution within each individuals in the population which then selects for cells which can specifically respond to the pathogen you are infected with (like brute-forcing a password). The origins of this system are debated, but I have not encountered anything which suggests that natural selection could not generate such a system. You have to keep in mind that you can often get 'jumps' in cellular functionality when pieces of viruses insert themselves in random parts of the chromosome. Viruses already have the ability to generate extreme diversity when they replicate within our bodies. So the thought is that one of our ancestors by chance had its reproductive cells infected by a virus in the exact region where an innate immune receptor existed, which gave this receptor the ability to generate new versions of itself during its lifetime. Natural selection would definitely be involved, because the virus probably inserted itself into lots of individuals in the population but in parts of the chromosome which did not lend themselves to creating this diversity in immune receptors. Hence, those individuals were selected out of the population, leaving the ones which had an ability to run this 'inner evolution' which we call the adaptive immune system.
It is kind of poignant that the solution to the age old problem of infection (adaptive immune system) likely resulted from a viral infection. Conversely, the adaptive immune system now works so well that it is probably selecting for even more sophisticated microbes which trick and evade it (https://pubmed.ncbi.nlm.nih.gov/15539148/). Which is all natural selection..
Some of the links in my previous comment might be useful to you: https://news.ycombinator.com/item?id=34405898
Edit: oh and technically it's much more complicated than that. The mucus layers which line your intestinal epithelium also play a key role in making sure that one bacteria cannot come along and chew up all of the nutrients. This is done by constantly generating new unique glycan (sugar) structures, so that the "wall" which separates us from our intestinal microbes never looks the same on any given day or time: https://academic.oup.com/gastro/article/7/1/3/5305718. This would probably fall in the innate immune system bucket.