What’s this about labelled tags?
I note that lots of icons have a nifty icon on them (Adobe, Android etc) how do you go about requesting one to be added to a tag?
Throw a sufficient amount of money at the SO team. They're sponsored tags.
you should contact the Advertising department of StackOverflow, handled by Inedo Media.
The contact form is at http://inedomedia.com/stackoverflow.aspx and you should mention you are interested in sponsoring a tag. This includes the icon, but also a list of sponsored link (See the Android Tag page for an example)
Be prepared to spend some money though, advertising isn't free.