Hey Cliff:
Yes T1 interfaces would suffice.
I found a document which explains connecting two Avaya PBX using cisco IOS 3745 gateway, probably you could use this to get an understanding
Also if you have any future problem post your questios in IP telephony forum instead contact center