General overview.
Each toxin and poison probably have their own evolutionary "arms race". Generally, an organism contains a compound that is a bit harmful to other species. As a predator or prey species becomes tolerant to low doses of this compound through natural selection, the compound efficacy could be increased (again by natural selection) on a molecular level, or at a dosage or concentration level.
Below are a few examples of where this has become the case, and some more general examples of how venom evolved in the first place.
Examples.
California Newt.
These newts contain tetrodotoxin (you may be familiar with this from the fugu fish). It is preyed on by a species of garter snake. This is a textbook arms race as the garter snake is naturally selected to have beneficial alleles that are tolerant to the toxin.
Dart Frogs.
The golden dart frog Phyllobates terribilis contains enough batrachotoxin to kill 10 people. That is apparently overkilling for any predator it would surely have to face especially given that the only animal alive that is immune to the poison is the frog itself. However, the snake Liophis epinephelus can tolerate massive doses of batrachotoxin (although I've heard it gets pretty poorly after eating a frog, rather understandably). These two species are locked in an arms race that drives the frogs to produce an unbelievably fatal cocktail and the snakes to become ever more tolerant.
Snakes.
Modified sweat glands evolved to damage the prey as much as possible for immobilisation, partial digestion, or defence. There are textbooks about snake venom and toxins. Here is a neat article I found with a cursory search or if you want to sink your teeth into the topic (heh.) check out this article.
Long story short: venom sacks are modified saliva glands from non-venomous snake ancestors. The diagram shows generally just how modified these apparatus have become!
Platypus
Let's not forget the weird and wonderful monotremes. It's hard to pinpoint exactly what drove the platypus to develop venomous barbs on its elbow (last time I looked into it, it was still disputed if they were for defence or hunting).
But what we can learn from this is that venom can independently evolve. Although the venom producing proteins are different, they produce the same venom as some snakes.