Свою карьеру хоккеиста Бастиансен начал в команде «Фриск Аскер», игравшую в норвежской элитной серии. В её составе Андерс отыграл 8 сезонов, став вместе с клубом чемпионом Норвегии сезона 2001/2002. По окончании сезона 2003/2004 Бастиансен отправился во вторую по значимости лигу в Швеции. По ходу сезона 2005/2006 Бастиансен перешёл в клуб Элитной серии Швеции «Мура». Здесь он отыграл три сезона, после чего перешёл в состав более сильной шведской команды «Ферьестад». В клубе из Карлстада Андерс отыграл 6 сезонов, за время которых сумел с командой дважды завоевать чемпионский титул. Сезон 2014/2015 Бастиансен провёл в Австрии в клубе «Грац Найнти Найнерс». Летом 2015 года Андерс принял решение вернуться в Норвегию и вновь начать выступать за «Фриск Аскер».
В составе молодёжной сборной Норвегии Бастиансен принял участие в двух чемпионатах мира в группе B. Свои выступления за основную сборную Андерс начал в 2005 году. За сборную Бастиансен выступал на 10-ти чемпионатах мира элитной группы. Дважды Бастиансен принимал участие в зимних Олимпийских играх, отыграв в общей сложности 7 матчей, в которых забросил одну шайбу.