I learned regular expression from the regular-expression.info site and from the first 4 chapters of Jeffrey Friedl's book over 5 years ago. I don't recall an introduction to NFA/DFA from them either. I'm pretty comfortable with regex and use them regularly (no pun intended) and so far, I don't feel that I've missed much.
I'm not disagreeing with your view, but I think it's worth pointing out from someone having developed an understanding of regex from a different perspective, that NFA/DFA might not be such a strong prerequisite and people should not feel like they're going in at a disadvantage.
It also helps you write optimal regular expressions - for instance if your regular expression clearly describes a DFA, then it will probably perform well. Otherwise in many cases you can optimize it - just as you can turn any NFA into a DFA.
It isn't so clear and cut these days however, as the regexp capabilities provided by modern libraries exceed the capabilities of finite state machines - for instance the engine in Perl 5.10 has support for recursion, which means a regular expression in Perl 5.10 can describe a Pushdown Automaton (PDA) instead, so things get way more complicated.
Either way, I suggest you do some reading on Automata Theory, because it's fun and not that hard.
Many people start out tweaking config files, editing other's scripts, manipulating logs and output data, and then eventually sit down and say "Damn, it's about time I learned how to really write good [bash/perl/python/regex]". I find the theory behind it interesting, but it's a bit of a distraction for many.
To a newcomer, even a naive implementation of NFA/DFA doesn't make sense. Consider this small gist https://gist.github.com/1414061
I have a feeling a newcomer will come out none the wiser even if he were shown this. And this is just a naive implementation - no nfa to dfa conversions, inefficient implementation etc.
I would root for state diagrams though. Generally diagrams help people see patterns mere text doesn't.
I'd be more concerned about making sure there is some discussion of nonregular languages; this appears to be in the works (I'm curious to see what exactly it turns out to be).
Edit: ahh, I see now mentioned in intro that "I'm going to be very practical and straight forward about it. No NFA to DFA conversion. No crazy explanations of push down finite state automata." :) I still argue that thinking of regex as state machines is a very useful tool.