I think the premise is a bit wrong. You build loyalty; rewarding it is a byproduct of building it.
Back in the early days of Starbucks in Chicago, regulars were recognized by the staff. There'd be some chitchat. Apparently, cost accounting was not yet so anal retentive, and a staff member would occasionally comp you your drink or something else. If there was a dispute, "the customer is always right".
Regulars really seemed to respond to that. Starbucks was not just about the coffee (or the mocha and sugar). It was a daily social experience.
You might call the comping rewarding loyalty. I'd call the social interaction and comping building loyalty. It made Starbucks a place customers wanted to be. Not just for the coffee; for the larger experience.
In a technical world, I think building loyalty has to do with offering a quality product and making product and knowledge acquisition as easy and streamlined as possible. For the social component, an active and informative community is hard to beat. Such communities need leaders. You can offer the leadership -- Look and PG and the moderators' effect here. Hopefully a community with coalesce.
As for product and information, there has been a lot of discussion here. Minimize sign up hassles and make sign up a late-binding feature in your flows. Use a site design that organizes, is easy to read/view, and otherwise gets out of the way.
Don't make your clients/customers jump through hoops. Don't make me solicit a friend in order to get a benefit. If I truly value your site, I'm going to tell my friend about it, regardless. What are you offering? Do that as well as possible. I'll keep coming back. And make sure you understand what you are offering. E.g. Are you just selling coffee? Or are you giving your customers a daily social routine?
Another example: Amazon, NewEgg, and some of the other, better online retailers. Is it just the product, price, shipping? Or is it also all the peer reviews and tips? Also, for me Amazon means worrying less about my credit card information. Their inclusion of third party sellers works well for me in this regard, in that I can order while having trust in the payment system.
In this case, I'd argue they are selling security (and convenience in ordering) as much as the product itself.
Free shipping is a nice perk (and I know shipping is just merged into the price, anyway). But it's the previous things that keep my coming back to Amazon.
It's not about rewards; it's about the original product. Really understanding what that is, and delivering it as well as possible.