These are not very documented, and at least at this writing, the informatives in the console were incomplete. Here’s the steps I have working at this writing, postulating the domain at hand being “emaildomain.com”:

1. First, in the O365 Exchange administrative console, go to the Protection area, and the rightmost tab is “dkim”, click on that. Then try to Enable any which are disabled. You will see an error message which says you need to create two CNAMEs. The two strings given, are the alias targets, the alias names are not given. Use these in the next step.

2. Set CNAMEs in Internet DNS. The alias names are the same every time; the targets are taken from the error message in step 1. They are not always entirely predictable, sometimes you will see “0i” buried within and there may be other variations. But the result will not be very distant from this:

selector1._domainkey.emaildomain.com
CNAME to
selector1-emaildomain-com._domainkey.emaildomain.onmicrosoft.com.
TTL 3600

selector2._domainkey.emaildomain.com
CNAME to
selector2-emaildomain-com._domainkey.emaildomain.onmicrosoft.com.
TTL 3600

3. Once your DNS changes have propagated thoroughly, go back to step #1 and try to enable DKIM again for the domain whose records you have just changed. If you have done your CNAMEs correctly, O365 will turn DKIM on. You may need to wait for DNS propagation.