I think it depends on your muscle mass how quickly you'll see results. For example, my legs are just chock-full of muscle, and in the past when I've started a new leg workout, I see results within a couple of workouts. On the other hand, my arms and back are my weakest (least muscular) areas. I can do several arm and back workouts without seeing a whole lot of change. I can feel it, but I can't see it.
I get my best results by incorporating vigorous step workouts intermittently with weight work. One night, aerobics; next night, weights, next night, both; then back.
Just remember, don't work the same body part two days in a row. I was told that there was one exception to this rule, though: I heard that you can do abs every night as long as you're not going for killer ab workouts.