Appreciation of problem structure is critical to successful learning. Two experiments investigated effective ways of communicating problem structure in a computer-based learning environment and tested whether verbal instruction is necessary to specify solution steps, when deep structure is already embellished by instructional examples. Participants learned to solve algebra-like problems and then solved transfer problems that required adjustment of learned procedures. Experiment 1 demonstrated that verbal instruction helped learning by reducing learners' floundering, but its positive effect disappeared in the transfer. More importantly, students transferred better when they studied with examples that emphasized problem structure rather than solution procedure. Experiment 2 showed that verbal instruction was not necessarily more effective than nonverbal scaffolding to convey problem structure. Final understanding was determined by transparency of problem structure regardless of presence of verbal instruction. However, verbal instruction had a positive impact on learners by having them persist through the task, and optimal instructional choices were likely to differ depending on populations of learners.