I'm planning on writing up a blog post exploring the attack and possibilities, but from a high level:
When you pass data into a regex engine for matching, it works character-by-character. When it reaches a character that doesn't match, the matching is terminated. That means that if you have the regex /^foo$/, "f" will take slightly longer to parse than "b", since it'll move on to the next character for "f", but not "b".
Due to this, you can produce matching data for a regex in a fairly small number of samples. Interestingly, it takes fewer samples to reliably get characters further down the string -- however, this may be a result of my horrid statistics code. Not sure yet.
As far as I'm aware, no one has ever done this before.