Collecting the Files

First and foremost you should download a version of CyanogenMod you want to install as well as an extended recovery mode that allows you to install non-verified ROMs. There are various options to choose from though I picked Cyanogen Recovery since it is maintained by the same people that develop CyanogenMod. Both files are available on the CyanogenMod download page. It is important that you choose the version specifically made for your device.

Furthermore you will probably want to have access to the Play Store. You can get Google Apps distributions of various extent at OpenGApps. For the S4 you have to select the ARM platform, the android version that you want to install, 5.1 as of the 27th of December, 2015. This should leave you with the following files, though possibly more current versions.

$ ls
cm-12.1-20151117-SNAPSHOT-YOG7DAO1JN-jfltexx-recovery.img
cm-12.1-20151117-SNAPSHOT-YOG7DAO1JN-jfltexx.zip
open_gapps-arm-5.1-pico-20151225.zip

To prepare for the actual installation you should now transfer the OpenGApps and the non-recovery CM files to your SD-card. You will later have to locate these with a rudimentary file explorer, so better put them in the root directory.

Flashing

Following these preparations, you have to flash an extended recovery mode onto your mobile phone because the provided one does not allow the installation of non-verified ROMs. For this I used heimdall, a reverse-engineered implementation of a Samsung-internal USB protocol for low-level control of android devices. Most importantly it lets you inspect your phones partition table and flash images onto them.

heimdall communicates with your phone in download mode, a special mode of operation. You enter it by powering off your phone and then restarting with Volume Down + Home + Power while only releasing the last one when the phone vibrates. If it worked, you should see an android logo and a confirmation question that asks if you really want to enter download mode (Yes, you want to). Then connect it to your computer via USB.

As a precaution you should first check your partition information table (PIT) and look for the recovery partition, i.e. the one that stores the recovery mode. In my case it was called RECOVERY but I have seen posts where it was called SOS. It is very important that you pick the right one. A mistake here can leave your phone unbootable.

$ heimdall print-pit --no-reboot # ... --- Entry #20
--- Binary Type: 0 (AP) Device Type: 2 (MMC) Identifier: 21 Attributes:
5 (Read/Write) Update Attributes: 1 (FOTA) Partition Block Size/Offset:
10166856 Partition Block Count: 20480 File Offset (Obsolete): 0 File
Size (Obsolete): 0 Partition Name: RECOVERY Flash Filename: recovery.img
FOTA Filename: # ...

Once you have identified the recovery partition, use heimdall to flash Cyanogen recovery. --RECOVERY is -- followed by the Partition Name of your recovery partition. --resume makes it reuse the existing download mode session.

heimdall flash --resume \
    --RECOVERY cm-12.1-20151117-SNAPSHOT-YOG7DAO1JN-jfltexx-recovery.img

Installation

Finally we get to the actual installation. Start your phone in recovery mode this time with Volume Up + Home + Power again keeping the first two pressed down. In the recovery menu select Install from ZIP and navigate to the ZIP-files you transferred to the SD-card during preparation. You can install them by clicking on them with the power button. Remember though that the order is important, CM first, then OpenGApps and ultimately power off and start normally.

If you made it to this point, you voided your warranty, but installed a mobile operating system without bloatware and some nice privacy built-ins.