1 of 2

You have to change the positioning keys of the corresponding edges. See the comments in the code.

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
    \usetikzlibrary{
        arrows,
    }
\begin{document}
\begin{tikzpicture}[
    ->,
    >=stealth',
    auto,
    semithick,
    node distance=3cm,
    state/.style={
        circle,
        draw,
    },
]
    \node[state]    (x0)                    {$x_0$};
    \node[state]    (x3)[above right of=x0] {$x_3$};
    \node[state]    (x4)[below right of=x0] {$x_4$};
    \node[state]    (x1)[right of=x3]       {$x_1$};
    \node[state]    (x6)[right of=x4]       {$x_6$};
    \node[state]    (x2)[below right of=x1] {$x_2$};
    \node[state]    (x5)[below right of=x2] {$x_5$};

    \path
    (x1) edge[loop above]   node{$1/2$}  (x1)
         edge[above]        node{$1/2$}  (x3)   % <-- changed from left to above
    (x0) edge[loop left]    node{$1/3$}  (x0)
         edge[bend left]    node{$1/3$}  (x3)
         edge[bend left]    node{$1/3$}  (x4)
    (x3) edge[loop above]   node{$1/2$}  (x3)
         edge[bend left]    node{$1/2$}  (x0)
    (x2) edge[loop right]   node{$1$}    (x2)
    (x5) edge[loop left]    node{$1$}    (x5)
    (x4) edge[bend left]    node{$1/2$}  (x0)
         edge[bend right]   node{$1/2$}  (x3)
    (x6) edge[left]         node{$1/3$}  (x1)
         edge[above left]   node{$1/3$}  (x2)   % <-- changed from left to above left
         edge[above]        node{$1/3$}  (x4);  % <-- changed from right to above
\end{tikzpicture}
\end{document}

image showing the result of above code