When should a tag be created?
Tags should only be created if there is a clear need for them, such as if it represents a new concept that has not been asked on the site before, but is still on-topic for the site. For example, on Stack Overflow, if a new programming language has been created and is in wide use, but no one has asked any questions about it, a new tag should be created for it.
When should I not create a tag?
Don't create tags just for the sake of creating tags. You should use existing tags as much as possible, because people follow those existing tags, and this increases the likelihood of getting a good answer. Don't create tags that are meta tags, or tags that describe the nature of the question rather than its topic. Don't create tags that are overly broad or ambiguous, or cannot be used as the sole tag on any question. Finally, don't create tags if the same tag has existed before, but was removed due to a community decision.
How do I create a tag?
To create a tag, one must apply it to an existing question. Any user with the Create Tags privilege (300 on most sites, 500 on Meta Stack Exchange, 1000 on Mathematics, and 1500 on Stack Overflow) may add new tags to any question at will by typing the new tag into the question's tags field, and submitting the post or edit1.
If you have enough reputation to create the tag
If you think there is a clear need for a tag, go ahead and create it yourself. If the new tag causes controversy, you can always come back to your site's meta to ask the community to judge it.
If you are creating a new tag, you may be prompted about it before you can submit your edit or new post. This warning is enabled on a site-specific basis.
If you don't have enough reputation to create the tag
Ask the question with a remotely related existing tag, and then add a comment on your question. Say that you wanted to add the tag to the question, but do not have enough reputation. Please consider including a reason why you think this tag is appropriate. If someone with enough reputation agrees with you, they will be able to create the tag. Please delete your comment once this has happened.
As an alternative, you can request a new tag by starting a discussion on the per-site meta. Clearly explain that you don't have enough reputation to create a new tag. This gives other people the opportunity to discuss if a new tag is needed.
1 Exception: a small number of tags may have been blacklisted on your site because they're not suitable; these tags cannot be created.