Receiving mail servers ask two questions about every message: was it sent by a server allowed to send for this domain? (SPF) and has it been changed on the way? (DKIM). A domain that answers neither ends up in spam folders.
Both answers are DNS records. Your email service lists the exact ones to add under DNS records on its service page.
SPF
One TXT record on the domain itself, listing who may send mail as you:
v=spf1 include:_spf.provider.example ~allImportant
A domain may have only one SPF record. Sending from your mail provider and a newsletter tool and a shop? Put every include: in the same record — never add a second one.
DKIM
A TXT record holding a public key, on a name your provider gives you (something like selector._domainkey). Your mail server signs each message with the matching private key, and the receiver checks the signature against this record.
Copy the value exactly. One missing character makes every signature fail.
Adding them
See TXT records for the steps. Allow an hour or two before testing — the records have to reach the rest of the internet first.
Tip
Also send yourself a message from the new mailbox to an address at a big provider and open its "show original" view. It reports whether SPF and DKIM passed.