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).

Pictures









Update 1

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.

Update 2

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.
