I'm also figuring out how I want to work this. I think in my initial marketing push I'm going to give a 10% discount for any business I get directly from that and also outline my referral program which will probably also be 10%.
Another option is to give them a gift certificate to giftcertificates.com. It's great for when you're not sure what to give someone because they can redeem it for products or gift cards to the store of their choice or just for a Visa gift card to use like cash. They also have a business rewards program which might offer some sort of bulk discount.
In the past I've done things like Starbucks or Borders gift cards or, for one guy, a few pints of his favorite Ben and Jerrys flavor.
I try to be generic and be aware of what they like and will use.
ETA - for those who have referral programs, do you outline it on your website? Or how do you let them know?