Воспитанник пензенского хоккея начал свою профессиональную карьеру в 1998 году в составе родного «Дизелиста», выступавшего в Высшей лиге.

В сезоне 2000/01, после года, проведённого в ТХК «Тверь», Андрей дебютировал в Суперлиге в составе московского «Динамо».

Сезон 2001/02 Кузьмин провёл в самарском ЦСК ВВС, где в 55 матчах он набрал 23 (12+11) очка, получив благодаря этому приглашение от пермского «Молота-Прикамье». Тем не менее, проведя в Перми лишь 11 матчей, в середине сезона 2002/03 он вернулся в Высшую лигу, подписав контракт с нижегородским «Торпедо».
 
Однако карьера в новом клубе у Андрея не задалась, и перед началом сезона 2004/05 он принял решение вернуться в родную Пензу. После того как в 106 матчах за клуб Кузьмин набрал 63 (26+37) очка, на него вышел нижнекамский «Нефтехимик», где он успешно выступал на протяжении последующих двух сезонов. Перед началом дебютного сезона Континентальной хоккейной лиги Андрей, будучи одним из лучших бомбардиров нижнекамского клуба, был обменян в казанский «Ак Барс» на Евгения Рясенского и Игоря Мусатова.
 
Однако в Казани Кузьмин не смог выйти на свой уровень; он получал мало игрового времени, вследствие чего в 39 матчах за клуб он набрал лишь 5 (4+1) очков, и, несмотря на завоёванный вместе с командой Кубок Гагарина, после окончания сезона он покинул «Ак Барс», вернувшись в «Нефтехимик».

Сезон 2009/10 Андрей начал очень неудачно — в 19 матчах он сумел набрать лишь 1 (0+1) очко, после чего он был обменян в московский «Спартак» на Алексея Заварухина. В «Спартаке» Кузьмин провёл оставшуюся часть сезона, набрав 10 (3+7) очков в 23 матчах, однако 5 мая 2010 года он покинул клуб, приняв решение вернуться в «Торпедо».
 
Однако в нижегородском клубе у Андрея вновь не пошла игра — в 34 матчах он набрал лишь 5 (4+1) очков, поэтому 4 января 2011 года руководство «автозаводцев» приняло решение расторгнуть контракт с игроком, после чего он вновь вернулся в родной пензенский клуб, который выступал в ВХЛ. В Пензе Кузьмин сумел набрать 22 (11+11) очка в 24 проведённых матчах, после чего его пригласила на просмотр череповецкая «Северсталь».
 
Тем не менее, не подойдя череповецкому клубу, 3 сентября он заключил однолетнее соглашение с новокузнецким «Металлургом».

24.01.2001
Накануне старта второго этапа первенства страны произошел ряд изменений в составе экс-чемпиона "Динамо". В тихоновский ЦСКА отправился хорошо знакомый с этим клубом центрфорвард Александр Харламов. Правый крайний Андрей Кузьмин продолжит выступления в динамовском фарм-клубе в Твери. Вернувшийся из аренды из Новокузнецка форвард Владимир Поздняков вместе с Олегом Смирновым тут же отбыл в саратовский "Кристалл". Закончился срок аренды и у игравшего за "Динамо" в прошлом сезоне молодого защитника из Казахстана Алексея Литвиненко - на первом этапе первенства он выступал в Екатеринбурге, сообщает корреспондент "СЭ" Алексей ЛАПУТИН.