Since it is possible to track the transactions in Bitcoin, is it possible to devise loyalty schemes?
As Nate already mentioned bitcoin operates in a totally trustless manner that emphasizes its users' pseudonymity. That means that the buyers would have to voluntarily identify themselves and all that is needed in this case is their unique identifier in this loyalty program which would allow them to keep their personal data secret but also benefit from this loyalty service, which could be as simple as an alphanumeric that they would have to enter during the checkout.
The drawback in this case from the service's perspective is that it cannot have any serious control over the cases where a single registration would be reused by more than one individuals who would want to take advantage of the service's logarithmic offerings associated with the total amount spent in a given period of time, so it should be designed in a way that consolidated purchases would not allow for significantly more benefits than those offered for the same amount of money when spent by two or more user accounts.
Another thing to take into consideration is that it would also require a user interface where the buyers could enter their loyalty service unique identifier, so it's ideal for online business but it definitely makes things a bit more obscure for brick-and-mortar businesses.
The difficulty with such a scheme would be identifying the customer.
Certainly, the loyalty program operator can monitor incoming transactions to addresses registered by participating merchants. But the public blockchain shows only the address from which the payment was made. The question is how to use that address to identify the customer who should be given points.
If the customer made all their payments from a single address, they could simply register this address with the loyalty program in advance. However, most wallet clients don't work that way; users hold their coins in many different addresses, and new addresses are created (for change) every time another transaction is made. (The thought is that this makes it harder to tell who a given address actually belongs to, and improves anonymity.)
So a customer would either have to register a large and constantly changing set of addresses (awkward) or would have to take steps to ensure that payments to the merchant were always made from one particular address that they had registered (not easy to do in most clients, and might require extra transactions and fees to move the coins to the proper address before making a payment).
There is a similar issue in that merchants should also want to use a large number of different addresses for incoming payments. If all incoming payments go to the same address, it makes it easy for a competitor to see how much business they are doing. Also, for safety they may not want to hold all their coins in a single address, so if all incoming payments go to a single address, they would need to make extra transactions later to spread them across other address. So ideally, each customer makes their payment to a unique address. Thus, it's not as easy as having each merchant register a single payment address. They would probably want to pre-generate a large number of addresses and register all of them.