Родился 26 февраля 1961 г. в Калининграде в семье Леона Таранды и Галины Соловьевой. Его отец был полковником Советской армии. После развода родителей проживал в Воронеже с матерью, работавшей бухгалтером в городском театре оперы и балета.
В 1974 г. Гедиминас Таранда поступил на классическое отделение Воронежского хореографического училища. Через два года перевелся в Московское академическое хореографическое училище (ныне Московская государственная академия хореографии). Занимался под руководством педагогов Аллы Богуславской и Игоря Уксусникова. Окончил училище в 1980 г.
В 1980-1993 гг. Гедиминас Таранда был артистом балетной труппы Государственного академического Большого театра. Среди его партий: Яшка в "Золотом веке" Дмитрия Шостаковича, Абдерахман в "Раймонде" Александра Глазунова, Ганс в "Жизели" Адольфа Адана, Визирь в "Легенде о любви" Арифа Меликова, Северьян в "Каменном цветке" Сергея Прокофьева.
С 1994 г. Гедиминас Таранда является генеральным директором и художественным руководителем труппы "Имперский русский балет". Основу коллектива составляют выпускники ведущих балетных школ России. Репертуар труппы сочетает классические балетные постановки ("Дон Кихот", "Кармен", "Лебединое озеро" и др.) и современные программы.
С 1996 г. на базе "Имперского русского балета" работает Академия балета Гедиминаса Таранды.
В 2004 г. Гедиминас Таранда исполнил заглавную роль в спектакле "Учитель танцев" по пьесе Лопе де Веги, поставленном режиссером Юрием Ереминым в Государственном академическом театре им. Моссовета.
В 2008 г. был участником проектов Первого канала "Ледниковый период" (в паре с фигуристкой Ириной Слуцкой) и "Король ринга", в 2011 г. на том же канале выступал в качестве члена жюри танцевального шоу "Болеро".
Преподаватель факультета искусств Российского государственного социального университета, заведующий кафедрой концертно-исполнительского мастерства.
Заслуженный деятель искусств РФ (2004).
Женат. Супруга - Анастасия Таранда (род. 1982, артистка балета, директор Академии балета Гедиминаса Таранды). Дочь - Дейманте (род. 2004). Также у Гедиминаса Таранды есть дочь Елизавета (род. 1994, солистка труппы "Классический русский балет"). Ее матерью является журналистка Марина Баранова.