В своё время «Вест Бромвич Альбион», за который он начинал играть в детстве, отказался подписывать с ним профессиональный контракт, сочтя Андерсона «бесперспективным». Пол заключил соглашение с «Халл Сити», где его заметили скауты «Ливерпуля». В январе 2006 года он подписал постоянный контракт с мерсисайдцами, а в обратном направлении отправился Джон Уэлш. По результатам этой сделки «Халл» может получить до 1 миллиона фунтов в зависимости от того, будет ли Пол играть за первую команду «Ливерпуля», что тем более примечательно, если учесть, как легко расстался с ним «Вест Бромвич».
Андерсон был одним из игроков юношеской команды клуба, которая в 2006 году выиграла Молодёжный Кубок Англии. В феврале 2006 он был впервые призван в первую команду, но в матче Лиги Чемпионов против «Бенфики» на поле так и не вышел.
15 июля 2006 состоялся дебют Пола в «Ливерпуле» - в предсезонном матче против «Рексхэма» он уже на пятой минуте забил гол, замкнув передачу Йона-Арне Риисе. Матч закончился победой «красных» со счётом 2:0.
26 июля 2006 года он продлил контракт с клубом ещё на три года (до лета 2010).
Он уже вызывался в юношескую сборную Англии.
После его перехода из «Халл Сити» он неоднократно демонстрировал столь хорошую игру (в том числе в Молодёжном Кубке Англии), что за ним закрепилось слава «нового Майкла Оуэна». Андерсон действительно умеет играть на острие атаки, однако предпочитает выступать на позиции вингера.
Рафаэль Бенитес сообщил однажды, что считает Андерсона одним из тех игроков, которые скоро смогут пробиться в основу.
7 июля 2007 года появились сообщения о том, что «Суонси Сити» собирается взять игрока в годичную аренду, и 16 июля валлийский клуб подтвердил эту информацию. В сезоне 2007/08 годов Андерсон являлся постоянным игроком первого состава этого клуба. По итогам сезона болельщики «Суонси», завоевавшего путёвку в Чемпионшип, признали Пола лучшим молодым игроком своей команды.
Перед началом сезона 2008/09 за право взять Андерсона в аренду на год спорили «Суонси» и «Ноттингем Форест». Обе команды завоевали путёвки в Чемпионшип в мае 2008 года, причём «Суонси» занял первое место, а «лесники» - второе. Хотя крайнюю заинтересованность в услугах Пола проявляли обе команды, он предпочёл «Ноттингем Форест» клубу, в котором провёл предыдущий сезон. А 1 июля стало известно о том, что Андерсон продлил контракт с «Ливерпулем» до 2011 года.
30 июня 2009 года стало известно о том, что Пол перешёл в «Ноттингем Форест» на постоянной основе, подписав с клубом контракт на три года. Сумма трансфера составила 250 тысяч фунтов. Сам футболист сообщил, что считает свой новый клуб достаточно сильным для того, чтобы уже в ближайшее время выйти в Премьер-лигу.