In addition to the good options Ian offered of dragging labels to the emails and using the list with the mouse as a multi-selector, there is also a way to speek this up with the keyboard.
While typing labels you can accept the current one by pressing enter instead of switching to the mouse to click. You do NOT have to even type the full label, as you type the nearest match will be accepted on enter. If you have keyboard shortcuts turned on in your gmail you can label any open message or selection of multiple messages by pressing the l key. If your labels are unique enough that they don't usually share a first letter, this get's all labeling operations down to three key strokes. l > X > Return where X is the first letter of your label. L enters label mode, start typing until you have a label match, then enter to accept. Repeat to add another label by hitting L again.