We are going to be adding/upgrading Exchange. We have several servers for different domains. Each email domain has it's own server for compliance requirements. Our process was going to be to install new Exchange server in the existing organization, move the mailboxes, public folders, etc. Move server roles when finished. Decommission the old Exchange Server. At what point to do need to add DKIM and how do we handle the public DNS. Do we put in multiple DKIM in public? If so, how do we do that with the the txt record names, etc.?

There are two ways:
If all of your servers use our DKIM plugin, you can synchronize the setting by copy the json file:

Install EA DomainKeys on the first server, and create the domain(s), then open Dkim Config Folder by DKIM manager -> DKIM -> Open Config Folder. You can find [domain].json files.
Install EA DomainKeys on other servers, open Dkim Config Folder, and copy [domain].json files from first server to other servers’ DKIM Config Folder.
Now, all of your servers have the same configuration (private/public key pair) for your domain.


another solution is:

you can use different selector for different server.

for example:

on old server, s1024 is the selector, and the public key is deployed to s1024._domainkey.yourdomain.
on new server, you can use snew as the selector, and deploy the new public key to snew._domainkey.yourdomain.

both DKIM can work fine.

https://www.emailarchitect.net/domainkeys/kb/dkim_exchange_2007_2010_2013.aspx#using-multiple-dkim-selector-with-the-same-domain-on-multiple-exchange-servers