The information is usually already publicly available : for examples the facebook graph api uses the same setup for some of their basic api methods (such as letting a site log you in through facebook) - base64 encoded json user data and an hmac signed with a private key + timestamp. Since the data is already publicly available (it's your facebook user id and other publicly available data), there's no need to use a more costly encryption algorithm. The hmac is there to confirm to the server who manages whichever associated online service that also created a facebook app you just gave access your profile to that this is good data, since they've got the secret on their end that the staff registered with on facebook. HMAC is fast.
No, it doesn't. No one should be using Blowfish for anything (except its key scheduler for bcrypt) and Blowfish is known to be slow as hell. A SHA-2 HMAC is basically identical in speed to AES-CTR. Sure, you want an HMAC on that, too, but whatever -- get a modern processor or an AES coprocessor. I guarantee this is not your performance bottleneck.
