I was thinking of doing a promotion where I give something like a free hat/mouse pad/t-shirt for new customers. Has anybody else ever done this? Think it will work?

IMO, the customer wants the hosting, not some hat/mousepad/tshirt. Seriously are they really going to sign up for that? Not really, If you are the worst host ever with no uptime etc offering a hat etc wont really promote sales. If your the best host out there, then you wont need to do that. SO imo that type of promotion is..... not practical. Maybe do like a free for a quater promotion with ur current client base.