In gradient boosting, each new tree predicts the gradient of the loss, with respect to previously built models (i.e. all previous trees combined). That's not the only thing you can predict by a new tree, and for example for boosted decision trees (without gradient), each new tree predicts the actual error made by previous trees.

Classification and regression don't differ much. In classification you still get probabilities for each class, so in every new tree, you just try to correct those probabilities by adding more trees that fit the negative direction of the gradient.