Карьера Карла-Хайнца началась в «Штутгарте», куда он попал из школы «Вальдхофа» в Мангейме. В 1976 году стал игроком «Штутгарта», дебютировав 20 марта во второй Бундеслиге матчем с «Байройтом», закончившемся вничью 1:1. В сезоне 1977/78 «Штутгарт» вышел в Бундеслигу и в ней Карл-Хайнц дебютировал 6 августа матчем с мюнхенской «Баварией». Матч закончился упорной ничьей 3:3.
Напарником Карл-Хайнца по защите в «Штутгарте» был его брат Бернд. Они оба принимали участие по чти во всех матчах «Штутгарта» и помогли клубу в сезоне 1983/84 выиграть чемпионат Германии. Всего Карл-Хайнц провёл за «Штутигарт» 311 матчей и забил 22 мяча.
Летом 1986 года перешёл в марсельский «Олимпик». Сумма трансфера составила 3,5 миллиона марок, что по тем временам было дорого за футболиста. В сезонах 1988/89 и 1989/90 Фёрстер помог марсельцам стать чемпионами Франции. Всего за «Марсель» Карл-Хайнц играл четыре сезона и провёл 130 матчей, забив в них 10 мячей.
Всего за сборную Карл-Хайнц провёл 81 матч и забил 2 мяча. Его дебют состоялся 5 апреля 1978 года в товарищеском матче с командой Бразилии, когда ему ещё не было 20 лет. Матч закончился поражением немцев со счётом 0:1, Карл-Хайнц на 77-й минуте, сразу после пропущенного мяча, заменил Бернарда Дица.
Со сборной Карл-Хайнц стал чемпионом Европы, а также двукратным финалистом чемпионата мира.
Сборная Германии
«Штутгарт»
«Марсель»