What to teach in a lab: Many students commented that it was difficult to concentrate on what some programs were trying to teach because there was so much other work for the program that had to be done. The key concepts that programs emphasized were sometimes lost in a sea of GUI's, bells, and whistles. Mini-labs can be used to abstract difficult concepts that will be needed in later projects. This way students can focus on learning the concepts before they have to apply them, leading to a greater understanding of what is being taught.
In addition to programming labs, we highly recommend creating non-coding labs. A design lab, for instance, would be very useful. The only downside is that these labs really do require a knowledgeable person to administer them, especially if you want to take full advantage of many teaching techniques, like CRC cards.
Where to start: The idea is to take the concept you want to teach and abstract it from all the rest of the support code. This forces students to concentrate only on what you want them to learn, as opposed to getting lost in other aspects of the program.
What to do: Once you have identified the concept you want to teach, you need to figure out in what context you want to teach it. For instance, Saul used racecars to demonstrate the holder pattern. Students only had to write the holder class, but once they wrote that class they had a fully functional demo. The idea is that students can write the essential part of a larger program, hence learning the concept without having to waste all the time doing the legwork (designing it, making GUI's, etc.).
Time constraints: The labs we designed are mini-labs, and we feel that they should take roughly an hour to do for someone who is utterly confused (the target audience). For someone who already understands the concepts, the labs should take no more than 10 to 15 minutes.