This is not encryption that you need. Well, you might need it too, but that won't do the whole job.
Encryption is for confidentiality: you encrypt the token if you don't want the client to learn the token contents, i.e. his permissions. Maybe you indeed want to hide that information from the client, but that's a secondary concern. The primary security characteristic that you wish to achieve is integrity: you don't want clients to be able to produce fake tokens and be granted entry. As a general rule, encryption does not provide integrity; for that you need a MAC, or a digital signature. Encryption may, as a by-product, make data alteration a bit harder, but certainly not impossible.
Digital signatures are more generic, but heavier (higher size and CPU overhead). What digital signatures provide is the following: whoever verifies the signature needs not be able to generate other signatures; the verification and generation powers are disjoint. With a MAC, the same key is used to produce the MAC and to verify it, so the two powers are equivalent. In your case, the exta genericity of signatures may be unnecessary, because both servers are yours, so you can probably arrange for a shared secret key between both servers. However, you might want to use a signature so that an attacker who obtains a read-only glimpse of the data server (e.g. through an old discarded hard disk) does not obtain enough information to be able to fake tokens, and thus obtain all write accesses for all possible users in your system.
If you follow the simple road of a shared key, and you want both encryption and MAC, then you are encouraged to use an "encryption mode" which provides both, because decades of research have come to the conclusion that mixing encryption and MAC together is a complex endeavour, prone to catastrophic silent failures. So use GCM or EAX.
If you want signatures and encryption, then again this is not a light job. An extra complication is that the power to decrypt must be on the data server side, while signature generation will be on the info server. In this model, both servers would have their own key pair. The smart thing to do would be to use an existing format and library which handles the tricky points. I suggest OpenPGP; it is a well-studied format, and there are open-source implementations available (e.g. GnuPG, which has bindings in many frameworks).
Regardless of the model and implementation, absence of direct communication between your two servers necessarily gives some extra power to the client: an evil client may decide to send the token, or not, or send another token. Replay attacks are an illustration: the client may want to send an old token value, thus allowing him entry with privileges which have since then been revoked.
One method to block replay attacks is to embed in the token an expiry date (under the protection of the MAC or signature, of course: evil clients would love to be able to modify that date). This works, but implies an inherent latency: if you decide, on the info server side, to revoke the privileges of a given user, then the said user can still use his current token until its expiration. This can lead to uncomfortable situations: emergency stop buttons should work immediately, not "within 15 minutes".
You may want to separate authentication from authorisation. Authentication is about making sure of the identity of the client; authorisation is about deciding what a given client should be allowed to do. The login+password procedure is authentication. If the bulk of the "high traffic load" comes from the password processing (e.g. because you hash password with a good password hashing function, as you should), then you might want to offload authentication on the "info server", while keeping authorisation on the "data server". In that model, the token will contain "this is Bob", instead of "the holder of this token is allowed to read data elements 1 and 2".
With such a setup, you still have an immediate, no-latency method to block indelicate users. An evil user is still himself, so his authentication token can remain valid for a long time; and if a user's password is stolen and you notice it (almost always asynchronously), you still have the option to block that user on the data server until the crisis is resolved.
