How does Ubuntu know what programs exist and can be installed?

I typed the following in a terminal

$ musique
The program 'musique' is currently not installed. You can install it by typing:
sudo apt-get install musique

So Ubuntu knows that "musique" is a program, although it's currently not installed on the machine. However, if I type

$ musiquez
No command 'musiquez' found, did you mean:
 Command 'musique' from package 'musique' (universe)

it knows that there is no such program called "musiquez".

My question is, how does Ubuntu know this? Where is this information stored about what applications can be installed on Ubuntu?

This feature is provided by the command-not-found( Its function is to suggest alternatives and corrections in case of mistyping etc. ) package. Ubuntu installs it by default.

how does it work?

The way it works is through the command_not_found_handle() function in bash. bash provides a hook which is basically a function that is invoked when a command is not found.

If you are more curious, open the /usr/lib/command-not-found file and take a look at the script. It works using the python module CommandNotFound.

A pair of packages, command-not-found and command-not-found-data, are what makes this feature work.

command-not-found is simply a handler for the command_not_found_handle() bash function; it searches through the data about the mapping between commands and packages provided by command-not-found-data.