Labels aren’t (yet) supported for blogs using classic templates. If you want to use labels, you currently need to switch to a new Layouts template.

Update (9/14): You can now enter labels for your blog with a classic template. The labels will appear under the post body, and searching for labeled content works the same as for a layouts blog. However, there is no tag for adding all your labels to your sidebar. To use the sidebar labels widget, you'll have to switch to a Layouts template.