I am using Outlook 2011 with gmail. I moved to Outlook 2011 recently. Before that I was using web mail. When I moved to Outlook recently, I got all my labels with the emails. But now when I go the web mail and create a label, it does not come up as a folder in Outlook 2011. Similarly if i delete a label from Gmail, it does not come up in Outlook 2011.
PS - I used this link to set up my Outlook 2011 - http://www.macstories.net/tutorials/how-to-wrangle-outlook-2011-to-work-with-gmail/