Jeffrey Friedl's Mastering Regular Expressions is a brilliant book. Though the book as a whole is too advanced for non-programmers, the first chapter "Introduction to Regular Expressions" should prove interesting reading for a keen and intelligent non-programmer, explaining in detail how regular expressions work. Not only that, but you could use some of the many excellent examples from this book to help you teach the non-programmers.

Update: I just remembered japhy's CPAN module YAPE-Regex-Explain which might come in handy because it explains a regex in English. An example of its use can be found in Re: This looks like someone sneezed and hit the keyboard.