Make sure they know strings well (array of chars, series of bytes in memory, can be indexed, copied, broken up, what it looks like, what ASCII is, etc).

From then on, a regex is really just 'try this. if it doesn't work, go back and try something else'. The language for defining the values for this algorithm are very intuitive when you grok strings, and it's only the complex stuff (shameless plug: Re: Parsing a macro language.. buaahahaha) that really needs learning. For that there are good books, perlretut, perlrequick, and for deep problems, perlre.

Good luck!