I didn't truly understand regular expressions until I saw how they are executed. There are simple algorithms for executing them, so that might not be such a bad way to teach.
I learned from the book The Unix Programming Environment but I also didn't truly understand regexp until I read how they were executed, in Programming in Standard ML the first chapter shows how to implement a complete package/parser for regexp http://www.cs.cmu.edu/~rwh/isml/book.pdf
