SPF is relatively easy (as long as you've got a static IP). DKIM isn't terrible, but it is frustrating. IIRC, you need to setup a milter in postfix and give that a key that you also need to put into DNS. After that, test it a bunch.

Then be sure to set a DMARC DNS record that advises recipients to require DKIM. Downside is your mail will bounce when you mess up DKIM, upside is you'll get somewhat clear feedback.