~ is $HOME, but sometimes?

~ is an alias for $HOME provided by a number of shells, but $HOME is more universal. $HOME actually asks the shell to insert (substitute) the environmental variable HOME here. There are quite a number of different environmental variable that can be substituted, try running env for a list. Note that ~ is not always recognized when it's not at the beginning of a word. Try these two commands for comparison:

ls /~
ls /$HOME

The first gets passed to the ls executable as /~ which then tries to look at a file called ~ in the root directory, the second expands $HOME and becomes //home/user which is then passed to the ls executable as a command-line argument. All POSIX systems (POSIX is the standard for how UNIX and Linux systems operate) allow multiple slashes to be treated the same as one slash so //home/user is the same as saying /home/user. ~username is a shortcut for telling the shell to look up username in the passwd file and return their home directory. There is no equivalent environment variable. All of these substitution are done by the shell and are supported by most of them, but only environment variables like $HOME are guaranteed to be supported by all shells. Also, cd is actually a built-in command. It's a special directive that tells the shell itself to change directories. It's not like other shell built-ins that can be implemented as a separate executable like echo is because it's used to change a fundamental attribute of the shell process. echo is merely a shell built-in for performance reasons, but in the good old days of UNIX, was only available as it's own executable /bin/echo.

~foo means 'the home directory of user foo'.

This isn't done by the kernel, it's interpreted by the shell. Whenever the shell sees ~foo as an argument, it transparently replaces it with the home directory of user foo and passes that in its place. So when you run cd ~tandu, the shell is actually running cd /home/tandu.

~ followed by a username expands to that user's home directory.