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 or a new question they're about to post. Any user with the Create Tags privilege (150 on beta and non-designed sites, 300 on most designed sites, 500 on Meta Stack Exchange, 1000 on Mathematics and Physics, and 1500 on Stack Overflow) may add new tags to any question at will1.
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 by typing the new tag into the question's tags field, and submitting the post or edit. 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.
Note: if there have been no questions asked about a certain topic you want to create a tag for, please hold off on creating the tag until you or someone else asks a relevant question about it. Don't just add the tag to a random question, and don't post a new "dummy" question just for the sake of creating the tag.
If you don't have enough reputation to create the tag
Ask your 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 blocked from creation on your site because they're not suitable; these tags cannot be created.