Immutable might not be the best term, its more atomic. And while you can install packages with rpm-ostree for example, it gets layered ontop, and the more packages you layer, the more likely an upgrade fails, or a rebase fails. Hence you build a custom image, or adopt a user-space solution.
The method to install applications is again, userspace focused ones. for GUI apps its Flatpak and AppImage. For CLI tools it can be appImage, but for others its Mise, Brew, asdf, or even Nix.
The antithesis is installing applications onto the immutable portion of the system, or messing with it in any way (by layer packages ontop of the immutable parts). Installing into userspace is the preferred method. So these "immutable distributions" do have ways to install "packages (programs)" and that is Flatpak, Brew, AppImage, etc and not the system package manager.
It is why they are moving away from even having Layering as an option.