Ubuntu – Where does apt-get install libqt4

Whenever you call apt-get update the repositories contained in the sources.list get read, this tells apt-get from where to get packages lists. This list get downloaded and stored in /var/lib/apt/lists for posterior use. These are lists of all packages available from the repositories you selected. Even if you remove your sources.list, this list will be available for APT. That's why you should always do update whenever you add/remove/modify a repository, to keep these lists updated.

How does the terminal know that chromium-browser is a valid package to install?

"The terminal" knows nothing. APT read all the lists in /var/lib/apt/lists and determine if the package is available. If the package is not found in any of the lists, you will get:

E: Unable to locate package <package>

Is there some list of all packages that can be installed?

This changes from repository to repository. Your local copy/list of your active repositories is found in /var/lib/apt/lists.

How does it find the packages?

$ sudo apt-get check
Reading package lists... Done
Building dependency tree       
Reading state information... Done

The line of interest is

Reading package lists... Done

which tells you that APT reads the list, from /var/lib/apt/lists.

I have exactely the same issue. I am trying to test my working setup with Ubuntu 16.04 and GTX1080 with CUDA 7.5 for parallel computing, and was hoping to easily get this done by using the packages provided in the repos. Unfortunately as noted above they are missing. It is possible to use the runfile install for installing only the samples. See e.g. for an older version:

https://stackoverflow.com/questions/27306724/ubuntu-14-04-how-to-install-cuda-6-5-without-installing-nvidia-driver

This works also for 7.5. Simply say "no" when prompted for driver and toolkit installation. You will also need to set the right toolkit libraries. This installs cuda samples into your home by default. However there seem to be an issue with libraries not being found as the package from the repo also puts them into a different location.

However some simple samples like matrixMul compile and run fine.

There might be a simple workaround by adding the right path, but probably installing at least cuda-toolkit together with samples from the runfile should make it work 'out-of-the-box' - have not tried it yet...