I'm not asking where to learn. I've found lots of good resources online, and books etc.

But how the heck do I tackle them. Where is the start of it, the end? When does the regexp processor advance on the text, when does it hold its stand and tries another match? etc.

I feel like trying to figure out hieroglyphs on the Egyptian pyramids.

I think that the knowledge of the Automata theory is critical for understanding.

Once you understand what an automaton is, and how regular languages are defined, understanding the regular expressions will be much easier. 

As to the specific syntax and differences between the various implementations... Well, some things you just have to remember. There are aids for that, too.

Edit

Some of the comments below raised important points:


Don't forget that regular expressions (as implemented in most programming languages) are a superset of regular expressions in automata theory. While a good theoretical background is a useful place to start, it won't tell you everything. (Thanks, David Thornley)
Multiple commenters say that it is possible to learn the various regex syntax without learning the theoretical basis. While it is true that you can learn syntax without fully understanding how it works, it was my impression that the full understanding is what the OP was after. The question was about the actual basis: when does the processor advance? When does it stop? How it decides that its a match? That's the basis, that's the theory, and it is based on the Automata Theory. Sure, you can drive a car without knowing how the engine works. But if you're being asked "how does the gas actually make it drive" - you have to talk about how the engine is built, don't you?

