Programming by Demonstration offers an intu- itive framework for teaching robots how to perform various tasks without having to preprogram them. It also offers an intuitive way to provide corrections and refine teaching during task execution. Previously, mostly position constraints have been taken into account when teaching tasks from demonstrations. In this work, we tackle the problem of teaching tasks that require or can benefit from varying stiffness. This extension is not trivial, as the teacher needs to have a way of communicating to the robot what stiffness it should use. We propose a method by which the teacher can modulate the stiffness of the robot in any direction through physical interaction. The system is incremental and works online, so that the teacher can instantly feel how the robot learns from the interaction. We validate the proposed approach on two experiments on a 7-Dof Barrett WAM arm.