Could you attach a nice (card) label with pretty ribbon and one of those teeny gold safety pins? You could do the details on computer, maybe even find a nice template somewhere? Or you could handwrite them, rubber stamp some kind of logo?
have a look at flickr - type in handmade gift tags, kraft tags that kind of thing and you'll find oodles of gorgeous (and some not so nice) gift tags. i'd love to be crafty that way but sadly I'm not, but I do spend way too much timeon flickr ogling other peoples creations.
I made a label with a magnet on the back for a knitted gift, so that the washing instructions could be kept on the fridge for future reference, as they won't be sewn into the item. Most craft shops sell either squares or a roll of magnets, which are soft enough to be cut to size