They could use the same server, or they connect their two Sametime servers (no need for a gateway), the servers just need to be able to see each other, and have the directories configured correctly.
http://www.ibm.com/support/knowledgecenter/SSKTXQ_8.0.1/com.ibm.help.sametime.801.doc/Standard/st_adm_mult_sync_st_svrs_t.html?lang=en