What's the difference between vim regex and normal regex?

I noticed that vim's substitute regex is a bit different from other regexp. What's the difference between them?

If by "normal regex" you mean Perl-Compatible Regular Expressions (PCRE), then the Vim help provides a good summary of the differences between Vim's regexes and Perl's:

:help perl-patterns

Here's what it says as of Vim 7.2:

9. Compare with Perl patterns                           *perl-patterns*

Vim's regexes are most similar to Perl's, in terms of what you can do.  The
difference between them is mostly just notation;  here's a summary of where
they differ:

Capability                      in Vimspeak     in Perlspeak ~
----------------------------------------------------------------
force case insensitivity        \c              (?i)
force case sensitivity          \C              (?-i)
backref-less grouping           \%(atom\)       (?:atom)
conservative quantifiers        \{-n,m}         *?, +?, ??, {}?
0-width match                   atom\@=         (?=atom)
0-width non-match               atom\@!         (?!atom)
0-width preceding match         atom\@<=        (?<=atom)
0-width preceding non-match     atom\@<!        (?!atom)
match without retry             atom\@>         (?>atom)

Vim and Perl handle newline characters inside a string a bit differently:

In Perl, ^ and $ only match at the very beginning and end of the text,
by default, but you can set the 'm' flag, which lets them match at
embedded newlines as well.  You can also set the 's' flag, which causes
a . to match newlines as well.  (Both these flags can be changed inside
a pattern using the same syntax used for the i flag above, BTW.)

On the other hand, Vim's ^ and $ always match at embedded newlines, and
you get two separate atoms, \%^ and \%$, which only match at the very
start and end of the text, respectively.  Vim solves the second problem
by giving you the \_ "modifier":  put it in front of a . or a character
class, and they will match newlines as well.

Finally, these constructs are unique to Perl:
- execution of arbitrary code in the regex:  (?{perl code})
- conditional expressions:  (?(condition)true-expr|false-expr)

...and these are unique to Vim:
- changing the magic-ness of a pattern:  \v \V \m \M
   (very useful for avoiding backslashitis)
- sequence of optionally matching atoms:  \%[atoms]
- \& (which is to \| what "and" is to "or";  it forces several branches
   to match at one spot)
- matching lines/columns by number:  \%5l \%5c \%5v
- setting the start and end of the match:  \zs \ze