The following loop is embarrassingly parallel:

https://github.com/scikit-learn/scikit-learn/blob/master/sklearn/ensemble/gradient_boosting.py#L552

Edit: I (@ogrisel) removed the Easy tag and put a Moderate tag instead. Based on the discussion below the most beneficial way to add n_jobs support for GBRT would be deep inside the Cython tree code (to benefit GB regression and adaboost models as wells instead of just GB classification).