How do I create a negated arrow on \xRightarrow?

Heiko Oberdiek's centernot package comes in handy for that:

\documentclass{standalone}

\usepackage{centernot}
\usepackage{mathtools}

\begin{document}
$\centernot{\xRightarrow{sdfkjhsdf}}$
\end{document}

The following test file adds new macros \x(n)(Left|Right|Leftright)arrow similar to the definitions of package amsmath. The negated arrows use help macro \narrowfill@ with the symbol \neq in the middle of the stretchable area of the arrow.

\documentclass{article}
\usepackage{amsmath}

\makeatletter
\newcommand*{\xRightarrow}[2][]{%
  \ext@arrow 0359\Rightarrowfill@{#1}{#2}%
}
\newcommand*{\xLeftarrow}[2][]{%
  \ext@arrow 3095\Leftarrowfill@{#1}{#2}%
}
\newcommand*{\xLeftrightarrow}[2][]{%
  \ext@arrow 3399\Leftrightarrowfill@{#1}{#2}%
}

\newcommand*{\xnRightarrow}[2][]{%
  \ext@arrow 0359\nRightarrowfill@{#1}{#2}%
}
\newcommand*{\xnLeftarrow}[2][]{%
  \ext@arrow 3095\nLeftarrowfill@{#1}{#2}%
}
\newcommand*{\xnLeftrightarrow}[2][]{%
  \ext@arrow 3399\nLeftrightarrowfill@{#1}{#2}%
}

\newcommand*{\nRightarrowfill@}{%
  \narrowfill@\Relbar\Relbar\Rightarrow\neq
}
\newcommand*{\nLeftarrowfill@}{%
  \narrowfill@\Leftarrow\Relbar\Relbar\neq
}
\newcommand*{\nLeftrightarrowfill@}{%
  \narrowfill@\Leftarrow\Relbar\Rightarrow\neq
}

\newcommand*{\narrowfill@}[5]{%
  $\m@th\thickmuskip0mu\medmuskip\thickmuskip\thinmuskip\thickmuskip
  \relax#5#1\mkern-7mu%
  \cleaders\hbox{$#5\mkern-2mu#2\mkern-2mu$}\hfill
  \mkern-5mu %
  #4%
  \mkern-5mu %
  \cleaders\hbox{$#5\mkern-2mu#2\mkern-2mu$}\hfill
  \mkern-7mu#3$%
}
\makeatother

\begin{document}
\begin{align*}
  A &\xRightarrow[below]{above} B      & C &\xRightarrow{} D \\
  A &\xnRightarrow[below]{above} B     & C &\xnRightarrow{} D \\
  A &\xLeftarrow[below]{above} B       & C &\xLeftarrow{} D \\
  A &\xnLeftarrow[below]{above} B      & C &\xnLeftarrow{} D \\
  A &\xLeftrightarrow[below]{above} B  & C &\xLeftrightarrow{} D \\
  A &\xnLeftrightarrow[below]{above} B & C &\xnLeftrightarrow{} D
\end{align*}
\end{document}

Remarks:

• The height and depth of \neq is automatically taken into account and the superscript and subscript are moved to avoid clashes with the slash.
• If package mathtools is needed, load it afterwards. It also defines \xLeftarrow, \xRightarrow, and \xLeftrightarrow, but IMHO the spacing of the versions of mathtools is too tight with possible visual clashes of the annotations with the arrow head.

The previous is solution somewhat buggy because you have to manually set the \kern length.
I would prefer to define a simple macro \NOT as in the following code:

\documentclass{standalone}
\usepackage{amsmath,amssymb}
\usepackage{mathtools}

\newlength{\NOTskip} 
\def\NOT#1{\settowidth{\NOTskip}{\ensuremath{#1}}%
            \hspace{0.5\NOTskip}\mathclap{\not}\hspace{-0.5\NOTskip}#1}

\begin{document}
\begin{equation*}
 A \NOT{\xRightarrow{bla}} C \NOT{\xleftarrow[\text{et caetera}]{}} Z
\end{equation*}
\end{document}

producing