Great question. I learned them through osmosis over many years of looking at them in other people's code and tinkering myself. I don't remember ever going through a tutorial or reading a book. Probably not the best way to learn them as it definitely took a long time to have a good grip on them and I was missing important pieces for a long time. For example, it was only relatively recently that I learned that you can turn off "greedy" when using .* by adding a ? after it.
If I recall correctly I learnt the basics from MSDN documentation and later more thoroughly when I first came across Perl. Either of these are pretty decent choices, too. :)
I find picking an actual context is really important to keep you motivated as learning about regexps can be tedious and prone to error. Probably the most fun regexp work I've done has been with Apache's mod_rewrite - using .htaccess files of course - because it's a great feeling to master something that useful that previously just seemed like magic.
this one is incomplete but gave me a really good foundation that makes it easy to fill in gaps when I need, and most importantly gets you that "thinking in regex" result mentioned above- http://regex.learncodethehardway.org/book/