For more information, check http://www.yarnbombing.com, a blog devoted to yarn bombing. There is also a newly published book on the subject called Yarn Bombing: The Art of Crochet and Knit Graffiti by Arsenal Pulp Press.
Step 1: Prep and Knitting
If you want your tag to look the best, take measurements of what you're going to tag first. You can then use newspaper to cut out a template. When you finish a piece of yarncraft, you can lay it down on the template and see if it will stretch to fit, or if strips or squares need to be knitted up and sewn on to give the tag the proper shape and size.
Then, knit. I like to use simple light post tags to experiment with stitch patterns I've come across. This week I played with diamond and ripple patterns, as well as a thin strip of basketweave stitching.