Then it was about knowing a situation or a problem when regexes would apply and knowing how to look up the things I needed to solve that problem. Some regex 'phrases' are good for grepping, others for find and replace. Some will help you swap names around, some to reformat phone numbers.
After a while the phrases give way to general understanding and certain things become fluent.
I still only really write short or basic regexes, but I use them all the time in editing text or doing things that are a little bit complicated but actually a short regex just turns it from a hard problem into an easy problem.