My GatherBy variation:
GatherBy[Transpose@{labels, list}, First][[All, All, 2]]
{{{1, 2}, {-3, 4}, {-9, 1}}, {{-1, 3}, {0, 1}}, {{5, 6}, {7, 8}}}
A possible drawback is that the result is not sorted by label. This is easy to change by doing
GatherBy[Sort@Transpose@{labels, list}, First][[All, All, 2]]
{{{-9, 1}, {-3, 4}, {1, 2}}, {{5, 6}, {7, 8}}, {{-1, 3}, {0, 1}}}
which sorts by label but destroys the initial intra-label ordering or by
Sort[Transpose@GatherBy[Sort[Transpose@{labels, list}, OrderedQ[{#1[[1]], #2[[1]]}] &], First][[All, All, 2]]
{{{1, 2}, {-3, 4}, {-9, 1}}, {{5, 6}, {7, 8}}, {{-1, 3}, {0, 1}}}
which keeps the initial order.