This is so that I don't have to struggle as much the next time around.
Step 1. Download the package for your flavour of linux from Citrix
Step 2. Install the package / tar file.
Step 3. Navigate to /opt/Citrix/ICAClient/keystore
Step 4.
$ sudo mv cacerts cacerts_OLD
$ sudo mkdir cacerts && cd cacerts
$ sudo ln -s /etc/ssl/certs/* .
Step 5. Downlad the xyz.pem file for your Citrix server
The following is an example of how to do it. Remember, your Citrix server is not citrix.com.
This is firefox, chromium and friends might do it differently.
Step 6. Save the xyz.pem file in /opt/Citrix/ICAClient/keystore/cacerts/ as xyz.cert (yes, the extension matter).
Step 7. run
$ sudo /opt/Citrix/ICAClient/util/ctx_rehash
Step 8. Rejoice
Step 9. Clear sessions and cookies to make it work. Curse, loudly, and take a deep breath.