How does a shell know home(s)?

In the case of csh and tcsh, it records the value of the $HOME variable at the time the shell was started (in its $home variable as noted by @JdeBP).

If you unset it before starting csh, you'll see something like:

$ (unset HOME; csh -c cd)
cd: No home directory.

For bash (and most other Bourne-like shells), I see a different behaviour than yours.

bash-4.4$ unset HOME; cd
bash: cd: HOME not set

The content of the $HOME variable is initialised by the login process based on information stored in the user database against your user name.

The information about the user name itself is not always available. All a shell can know for sure is the userid of the process that is executing it and several users (with different home directories) can share the same userid.

So, once $HOME is gone there is no reliable way to get it back.

Querying the user database (with getpwxxx() standard API) for the home directory of the first user that has the same uid as the one running the shell would only be an approximation (not to mention the fact that the user database could have changed (or the home directory being defined as a one time value) since the login session started).

zsh is the only shell that I know that does that:

$ env -u HOME ltrace -e getpw\* zsh -c 'cd && pwd'
zsh->getpwuid(1000, 0x496feb, 114, 0x7f9599004697)      = 0x7f95992fddc0
/home/chazelas
+++ exited (status 0) +++

All other shells I tried either complain about that unset HOME or use / as a default home value.

Yet a different behaviour is fish's, which seems to query the database for the user name stored in $USER if any or do a getpwuid() if not:

$ env -u HOME USER=bin ltrace -e getpw\* fish -c 'cd;pwd'
fish->getpwnam("bin")  = 0x7fd2beba3d80
fish: Unable to create a configuration directory for fish. Your personal settings will not be saved. Please set the $XDG_CONFIG_HOME variable to a directory
where the current user has write access.
fish: Unable to create a configuration directory for fish. Your personal settings will not be saved. Please set the $XDG_CONFIG_HOME variable to a directory
where the current user has write access.
--- SIGCHLD (Child exited) ---
/bin
+++ exited (status 0) +++


$ env -u HOME -u USER ltrace -e getpw\* fish -c 'cd;pwd'
fish->getpwuid(1000, 0x7f529eb4fb28, 0x12d8790, 0x7f529e858697) = 0x7f529eb51dc0
fish->getpwnam("chazelas")                                      = 0x7f529eb51d80
--- SIGCHLD (Child exited) ---
--- SIGCHLD (Child exited) ---
/home/chazelas
+++ exited (status 0) +++

SEGV when the user doesn't exist (https://github.com/fish-shell/fish-shell/issues/3599):

$ env -u HOME USER=foo fish -c ''
zsh: segmentation fault  env -u HOME USER=foo fish -c ''

So how does the shell know where is my/other_user home?

It doesn't. You're just not performing the experiment properly. As you can see from the C shell manual, the cd command changes to the value of the home variable if supplied with no arguments. If this variable is unset, it doesn't know where to change directory to and prints an error:

machine:~> set home=/
machine:/home/user> cd
machine:~> unset home
machine:/> cd
cd: No home directory
machine:/> 

You unset the wrong variable. It's not HOME, the environment variable, it is home the C shell's internal variable (initialized from the value of the former when the shell starts up, but otherwise an independent variable in its own right).