Where exactly are programs and files saved on a non-persistent live system?

The live system that comes with the Ubuntu ISO is an Ubuntu installation in a compressed file called filesystem.squashfs. This file has a filesystem of SquashFS¹ which is comparable to the ISO filesystem of CDs & DVDs, which can be mounted and used.²

This file is in the /casper/ directory of the CD. You can even mount this file same way you can mount ISO files.

This file gets mounted and loaded into memory during boot to be used as a live system. But the full file doesn't get loaded at once, but only the required portions/programs on-demand.

A Live System can create/change files of the media with the help of a Persistent File. The persistent file used in Ubuntu is named casper-rw and contain filesystem like ext3 or ext4 which are writable. In a bootable USB, this reside in the root of the drive.

This casper-rw persistence file is union mounted as a overlay filesystem, which means both the read-only filesystem.squashfs and read/writable casper-rw are mounted on /. Any files that are changed or created are saved in this writable filesystem of casper-rw. Thus effectively creating the illusion that the Live CD is writable, where actually they aren't.

So, answering your questions -

Where are these files actually saved?

Answer given above.

Are they loaded into the RAM, so the maximum available memory for the live system is actually the RAM capacity of the machine?

I suppose, by memory you are referring the Space. Your question is "So the maximum available space for the live system is acutally the RAM capacity of the machine"?

No. Maximum available Storage for a Live System is the size of the Persistent File (If there is any) + Swap Space (If they exists already) + RAM (It it needs to be used as Storage until reboot)

Are installed programs stored in the CPU cache or somewhere else entirely?

If you install program in Live system without a Persistent File, those will be in your Memory. If you Reboot, all will be lost. However, if you're using casper-rw persistent file, those will be saved in that file and will be available after next reboot (Provided that you didn't delete that file)

Or is that information possibly written on empty space of the CD medium?

No, It doesn't write on the CD Medium. As explained in the previous answer.

Hope you get your answers.

Notes:

1. SquashFS - It is a read-only file system that lets you compress whole file systems or single directories, write them to other devices/partitions or to ordinary files, and then mount them directly (if a device) or using a loopback device (if it is a file). Source

2. You can mount it using commands like sudo mount ./filesystem.squashfs /mnt -o loop

3. Union mounting is a way of combining multiple directories into one that appears to contain their combined contents. Source

It says non-persistent. So they do not "persist" (continue to exist) between reboots. What happens is that a part of the RAM is used as a RAM disk. Essentially, a part of your RAM is used to simulate a disk. That's all there is to, really. That's why you can create files on your /home/ubuntu during a LiveCD session. They just won't survive (=persist) after reboot.

I don't have a LiveCD handy, but try typing df -h in the terminal next time and look for the / mount point. Look at the device. It will most likely be something like tmpfs. (This one liner should give you the line you're interested in: df -h | grep \/$ )

Some reading about RAM disks.