Strongly agree with
ctrl-z about the regex coach, which, he didn't mention, is free and comes with an interactive walkthrough. See also editpad, which isn't free, but comes with a trial version, and is a "real" get-work-done type tool, unlike regex coach, which is more for just learning. Great tutorial included with editpad as well,
which is free. Basically the same functionality as emacs but more user friendly.... oh, and checking out the web site, I would try out
regex buddy as well, which seems to be similar to regex coach but more powerful, and non-free. As you can see in the screenshot, it tkaes a regex and breaks it down into the component parts, explaining each of the parts in english. Looks perfect for a handholding intro.