We are teaching Gherkin (for SpecFlow) in a similar way, how mrD has described it.
I think it is very important though, that the audience is familiar with the main intention of "Specification by Example", agile requirement analysis and BDD, so we usually start discussing the background first. We also show a sample Gherkin scenario and explain the very basics (like Given/When/Then/But and tables).
Than we take a simple example story (that is quite familiar to everyone), like "add items to shopping cart" (with some orientation, of course) and let them formulate the acceptance criteria in small groups.
After that every team shows / explains their solutions and we discuss the good and bad practices that were present. After the second team, you can see almost all of the most important (good or bad) practices appearing.
I also type in the concluded solution, and show here alternative ways of describing the scenarios (background, scenario outline, etc.). If there is enough time, I also show how to automate & implement the imagined functionality based on that. This also help to understand some important rules to follow, that makes the automation much easier.
Although, I never know upfront what will happen, usually this exercise is the best part of our BDD training.