Arthropods have 6 or more limbs and arthropods with 6 limbs appear to move faster than arthropods with 8 limbs so I wonder whether this might have something to do with fast and efficient locomotion. But, this is just a guess. I wonder what the official explanation is, if it exists.
Number of legs in terrestrial vertebrates
Not only do mammals have four legs but actually all terrestrial vertebrates (which include mammals) have four legs. There are slight exceptions though as some lineages have lost their legs. Typically snakes have no legs anymore. Apesteguia and Zaher (2006) discuss the evolution of snakes legs reduction and report a fossil of snakes with a robust sacrum. Cetaecea (whales and friends) have lost their hind legs but we can still spot them on the skeleton. See for example the orca (killer whale, easily recognizable to its teeth) on the picture below. Pay attention to the small bones below its vertebral column at the level on the left side of the picture.
I also want to draw attention to the importance of the definition of legs. I guess that we would call something a pair of legs if it is constructed using a similar developmental pathway than current existing legs. If we are using some broader definition, then a prehensile tail as found in some new world monkeys, for example, could be considered as a leg (but only a single leg, not a pair of legs obviously). A list of animals having a prehensile tail can be found here (Wikipedia).
Did you say Natural Selection?
I think (might be wrong) that you have too selectionist a view of evolution. What I mean is that you are wondering why mammals have four legs and you're looking for an explanation of the kind "because mammal have this kind of need of locomotion and for this purpose four is the most optimal number of legs". Consider the following sentence: "If there is a need, natural selection will find a way!". This sentence is wrong! Evolution is not that easy. This false view of evolution is sometimes referred to as panselectionist.
The reality is that it is not easy to evolve such a developmental pathway as drastic as having an extra pair of legs that are well integrated into the body of the carrier of this new trait. Such an individual would need a brain, a nerve code, a heart and some other features that are adapted to have extra legs. Also, assuming such a thing came to existence it is rather complicated to imagine how it could be selected for. To go slightly further, you have to realize that there are many stochastic processes in evolution (including mutation and random variation in reproductive success) and an organism is a piece of complex machinery and is not necessarily easily transformable to some other form that would be more efficient (have higher reproductive success). Often going from one form to another may involve a "valley crossing" meaning that if several mutations are needed, intermediate forms may have low reproductive success and therefore a high amount of genetic drift (stochasticity in reproductive success) to cross such valley of low reproductive success. See shifting balance theory. Finally, even if there is selection for another trait, it may take time for the mean trait in the population to shift especially if there is only little genetic variance. A complete discussion on why the sentence "If there is a need, natural selection will find a way!" is wrong would fill up a whole book.
Gould (1979) is a classic article on the subject and is very easy to read even for a layperson.
Why 4 legs?
Terrestrial vertebrates have four legs because they evolved from a fish ancestor that had four members that were not too far from actual legs (members that could "easily" evolve into legs). This is what we call a phylogenetic signal. The explanation is as simple and basic as that. You can have a look at the diversity of terrestrial vertebrates here (click on the branches).
Number of legs in invertebrates
Arthropoda (Spiders (and other chelicerata), insects (and other hexapods), crustaceans (crabs, shrimps…) and Myriapoda (millipedes) and Trilobite as well)) evolved from a common ancestor who had a highly segmented body. From this ancestor, many groups have fused some segments. In these taxa, each pair of legs is attached to a particular segment (I don't think the segments are still visible in spiders today). In insects, for example, all 6 legs are attached to the thorax but to 3 different segments of the thorax, the pro- meso and meta-thorax (see below).
As a side note, it is interesting to know that the wings in insects did not evolve from the legs (as it is the case in birds and bats). There are two competing hypotheses for the origin of insect wings. Wings either developed from gills or from sclerite (chitine plate, the hard part of the insect). When insect first wings, they actually evolved three pairs of wings (one on each segment of the thorax). At least one pair has then been lost in all modern species. In the diptera, a second pair of wings have been lost and are replaced by halteres, particularly easy to spot in craneflies (see below picture). In millipedes, the link between segmentation and legs is even more obvious (see picture below). You can have a look at the diversity of Arthropoda here (click on the branches).
Asking how likely it is for a given population to evolve a given trait is extremely hard to answer. There are two main issues: 1) a definition of the question issue and 2) a knowledge issue. When asking for a probability one always needs to state the a priori knowledge. If everything is known a priori, then there is nothing stochastic (outside quantum physics). So to answer the question one has to decide what we take for granted and what we don't. The second issue is a knowledge issue. We are far from having enough knowledge in protein biophysics (and many other fields) to answer that question. There are so many parameters to take into account. I would expect that creating a third pair of legs would need major changes and therefore one mutation will never be enough in order to develop a third pair of legs. But, no I cannot cite you any reference for this, I am just guessing!
Following the wings example in insects. Insects have had three pairs of wings. While some mutation(s) prevented the expression of the third (the first actually) pair many of the genetic information for this third pair remain in the genotype of insects as they still use it for the two other pairs. Taking advantage of that, Membracidae (treehoppers) developed some features using a similar biochemical pathway than the one used to develop wings. Those structures are used as protection or batesian mimicry.
Let's imagine that an extremely unlikely series of mutations occur that create some rodent with 6-legs. Let's imagine this rodent with six legs has a larger heart in order to pump blood to these extra legs and it has a brain that is adapted to using six legs and some changes in its nerve cord so that it can control its 3rd pair of legs. Will this rodent have higher reproductive success than other individuals in the population? Well… let's imagine that with its six legs, it can run faster or whatever and has a very high fitness. How would the offspring of a six-leg mother (or father) and a four-leg father (or mother) look like? Will it be able to reproduce? See the issue is that it is hard for such trait to come to existence because 1) it needs many steps (mutations) and 2) it is hard to imagine how it could be selected for. For those reasons, there exist no vertebrates with 6 fully functional legs.
Well, let's assume it does and in consequence, after 200 generations or so, the whole population is only made of 6-legged individuals. Maybe the species got extinct then and no fossil record has ever been found. This is possible. It is not because something has existed that we necessarily find something in the fossil record.
I think I might interpret your question as asking, not just why don't mammals have more than four limbs, but why arthropods have more variety. Insects have six, but others have eight, ten, or more.
Partly there are just many more species of arthropods. 80% of animal species are some sort of arthropod, and some lineages of arthropods are distantly related to each other because arthropods as a group have existed since the Cambrian period. With so many more species, it's no surprise that they've managed to tack on some extra variety.
Although it might seem that insects and spiders are more closely related than, say, humans and fish, the reverse is actually true. In fact, insects split off from other arthropods at approximately the same time that fish were diversifying into the three main lineages that would eventually become cartilaginous fish (sharks & rays), ray-finned ("regular") fish, and lobe-finned fish (coelacanths and lungfish). All of these things happened at approximately the same time, geologically speaking, at around 400 million years ago. Some ancient lungfish crawled up onto land a short while after, giving rise to land animals. So in light of this, it's not really surprising that arthropods would have so much diversity in body plan - you don't look much like a leafy sea dragon (I hope).
But perhaps another way of looking at it is in the difficulty involved in adapting the body plans of these different types of animals. Arthropods have segmented bodies. In some arthropods, especially the myriapoda (centipedes, millipedes and so on), there's a pretty straightforward arrangement of one segment to one pair of legs (excluding the head). Vertebrates have a segmented body plan too, but our segments aren't quite so well-separated. In vertebrates, a "segment" is approximately equal to one vertebra. So since vertebrates aren't in the habit of attaching a pair of legs to each vertebra, it's harder to grow more legs. Instead, vertebrates have internal skeletons, with the familiar hips and shoulders in land animals. Vertebrates do have good luck adapting the internal structure when they need to. Most use the traditional four-leg layout, but humans, birds, whales, and snakes have all made pretty significant changes to it. But internally, it's still the familiar hips and shoulders - even snakes still have the necessary bones. Given another few hundred million years, they might disappear entirely, but it seems like the basic bone structure is tough to change. Who knows, in a hundred million years, the far future descendants of snakes might end up with legs again, and grow six or eight instead of four!
So, overall, I'd say that the two main reasons are that the arthropod body plan is just a little more flexible due to its higher degree of modularity, and that different kinds of arthropods are actually more distantly related than you might expect.
The answer by Remi.B is excellent, I'll just attempt an explanation by way of gene networks:
In genetics we see new genes "linking" to the older genome by regulation pathways and by being "fit" only in the context of the existing genome. This has the effect of making the older genes indispensable. Change them and you rupture the whole mesh. If you want to increase the number of limbs, you'd have to take that up with the HOX genes, that control the basic body plan. These are awfully ancient, originating in the common ancestor of flies and humans . So as a rule of thumb, these genes will also be awfully hard to mutate without ruining everything.
Another line of reasoning is that the HOX genes not only appeared early in evolution, but they are also expressed early in the development of the embryo. When anything that goes on in development depends on what has preceded it, mutations in HOX genes has a bigger chance of ruining something than mutations that are only expressed late in development. I'm going out on a ledge here, but consider that the color of hair, skin and eyes of a human baby are often not fully expressed until months after its birth and consider also the range of harmless variations in these colors. These superficial colors don't affect anything else, so the corresponding genes are free to mutate into a great variety.
Here is a more morphologic, less genetic answer:
According to Sansom 2013, the 2 sets of paired appandages (shoulder and pelvic) was set in stone when agnathans transitioned into gnathostomes (ie. when the first vertebrate organisms began to evolve jaws, an anatomic change that allows for classification of different stages of history found in the fossil record). They found variations where an agnathan had a paired set of anal fins (sort of the 3rd set of paired appendage, since anal fins are typically unpaired).
Now, moving forward millions of years, the Sarcopterygii (lobe fin fish) evolved into the tetrapods (4 limbed land vertebrate including amphibians, reptiles, birds, and mammals), this pattern (2 sets of paired limbs) became immutable, though much less fundamental variation throughout the phylogenesis of the various tetrapods.
Sansom RS,Gabbott SE, Purnell MA. 2013 Unusual anal fin in a Devonian jawless vertebrate reveals complex origins of paired appendages. Biol Lett 9: 20130002.