Ordinarily I would go with Underdark's suggestion.
However, this issue is common for other situations where it is not relevant or possible to have all the data in one layer, so the question is worth a quick 'how to'. Navigate to the Legend Items tab and...
- select a layer
- click the pencil edit button and delete everything in the labellayer's item text popup so you have no layer heading at all.
- click the + icon to expand your layer and select the element you want to label (below the level of the layer)
- click the pencil icon again and type in your label.
QGIS will make your label follow your patch and it automatically 'packs' the patchs when you don't have any layer heading.
EDIT (before and after screenshots):