Re: So, presumably
The textbook example of this happening in short time scale is that of moths in England over the historical period known as the Industrial Revolution. Moths (nocturnal, so inactive during daylight) would rest against the bark of trees, appropriately camouflaged to the species of tree they preferred. Soot from the burning of coal ('dark satanic mills') darkened the appearance of trees in many areas, and this placed a strong 'selection pressure' on generations of moths- favouring those that exhibited a mutation that made them darker. Pale moths would be readily seen by birds and promptly eaten.
This happened in decades, if not years. Moths, like spiders, have many, many offspring.
If billions of years seems to short a time-scale, please do bear in mind that there are other mechanisms in place- not least sexual reproduction. Sex not only allows beneficial mutations to be shared around, but, in the case of this spider, could also accelerate the process: If a female exhibits a preference for a male spider that makes decoys, her offspring will not only have the genes for that preference, but also the genes for the subject of that preference.
Also, mutations don't have to create everything 'from scratch' every time... say for example, an animal population had colonised a perfectly cave system... there would no longer be a selection pressure to retain eyes. The genes for the eyes wouldn't be 'deleted', but rather they would no longer be preserved against random mutations- and over many generations the eyes would diminish and disappear. These mutations might be small, but would prevent the eyes from developing. An analogy would be changing a few bytes on your HDD's table of contents that would render it unreadable- but most of the HDD's data is still there. Should this blind animal population find itself in an environment with light, a few mutations over generations might reinstate eyes- the 'building blocks' are still there. By the same process, 'throwbacks' occasionally occur, such as humans with vestigial tails, or Julius Ceasar's five-toed war-horse.
A mutation might also be along the lines of changing 'Goto 10' to 'Goto 20', and thus place, say, an enzyme in the 'wrong' place. It is thought such a mutation replicated an enzyme found in the eye (to break down foreign substances) into the digestive tract of bovines, allowing them to break down cellulose and thus digest grass.
It is endlessly fascinating, and I would recommend Stephen J Gould over Richard Dawkins should you want to read more.