Given a graph G whose edges are labeled with one or more labels, the Generalized Minimum Label Spanning Tree problem seeks the spanning tree over this graph that uses the least number of labels. We provide a mathematical model for this problem and propose effective greedy heuristics and metaheuristics. We finally compare the results of these algorithms with benchmark heuristics for the related Minimum Label Spanning Tree problem.