I can achieve this thanks to this hint like so:

# In the hyperref section of the document preamble


But if I change my document so that it has a title page, and the TOC moves to page two, I'll need to change this. Is there a better way to link to the TOC? Adding a \label{} and then using a ref{} does not seem to work.

-

You could use \hypertarget to create an anchor on the toc page, for example at the beginning of the TOC page or turning the TOC heading into an anchor. Here's an example how you could do it:

\documentclass{report}
\usepackage{fancyhdr}
\usepackage{hyperref}
\pagestyle{fancy}
\fancypagestyle{plain}{% for chapter starting pages
\begin{document}
Title page
\cleardoublepage
\hypertarget{contents}{}
\tableofcontents
\chapter{One}
\chapter{Two}
\end{document}

-
Can you say why I get the "TOC" link only in the foot of the first page? – Hendrik Vogt Feb 19 '11 at 12:59
@Hendrik: that's a good observation! It's because only the first page has fancy page style, the other pages automatically got plain as they are chapter starting pages. It can be fixed using \fancypagestyle{plain}{...}. I'll add it to my example. – Stefan Kottwitz Feb 19 '11 at 13:17

There are several ways to do this. One would be to write the page number of the TOC directly into the .aux file as shown below. I'm sure there is a nicer, more higher-interface solution for that, but just right now (1am) I can't get it. The code below assumes that you want to link to the first ToC page and not to the title of it.

\documentclass{book}

\usepackage{hyperref}
\usepackage{fancyhdr}
\pagestyle{fancy}
\def\tocpage{1}% Default value will be set to correct one at \begin{document}

\begin{document}

Titlepage

\cleardoublepage % Important to get the page number right
\makeatletter
% Write directly to the .aux file:
\write\@auxout{\gdef\noexpand\tocpage{\number\value{page}}}%
\makeatother
\tableofcontents

\chapter{test}
\chapter{test}
\chapter{test}
\chapter{test}

\end{document}

-