layman inquiry into mechanics of evolution
The question is a very deep one, and the answer is 'it depends'. Organisms can in general only evolve by taking rather short steps through genome space, where each step is better than the last. This could mean one or two nearby basepairs change, or one or two segments of DNA get duplicated, inverted, deleted, etc. It's the DNA that evolution acts on, not the organism's 'qualities', or as we call them, it's phenotype.

In your example, there might be a single piece of DNA which when duplicated, causes the organism's number of legs to go from 4 to 6. In this case the mutation can happen and be selected for and extra legs can evolve. If however the evolution of new legs requires a lot of mutations, non of which are individually useful, then the trait won't arise before the intermediate mutations are selected away. 

What may happen instead is something more complicated. E.g. the many mutations for the new legs could initially arise because they are doing something different, and then gradually get selected for other purposes. 

In general though the problem of how organisms' move from one peak in the 'fitness landscape' to another is an ongoing topic of research.