Not all utilities that you can execute at a shell prompt need actually exist as actual executables in the filesystem. They can also be so-called shell built-ins, which means – you guessed it – that they are built into the shell.
The Single Unix Specification does, in general, not specify whether a utility has to be provided as an executable or as a built-in, that is left as a private internal implementation detail to the OS vendor.
The only exceptions are the so-called special built-ins, which must be provided as built-ins, because they affect the behavior of the shell itself in a manner that regular executables (or even regular built-ins) can't (for example set, which sets variables that persist even after set exits). Those special built-ins are:
break
:
continue
.
eval
exec
exit
export
readonly
return
set
shift
times
trap
unset
Note that cd is not on that list, which means that cd is not a special built-in. In fact, according to the specification, it would be perfectly legal to implement cd as a regular executable. It's just not possible, for the reasons given by the other answers.
And if you scroll down to the non-normative section of the specification, i.e. to the part that is not officially part of the specification but only purely informational, you will find that fact explicitly mentioned:
Since cd affects the current shell execution environment, it is always provided as a shell regular built-in.
So, the specification doesn't require cd to be a built-in, but it's simply impossible to do otherwise.
Note that sometimes utilities are provided both as a built-in and as an executable. A good example is the time utility, which on a typical GNU system is provided both as an executable by the Coreutils package and as a shell regular built-in by Bash. This can lead to confusion, because when you do man time, you get the manpage of the time executable (the time builtin is documented in man builtins), but when you execute time you get the time built-in, which does not support the same features as the time executable whose manpage you just read. You have to explicitly run /usr/bin/time (or whatever path you installed Coreutils into) to get the executable.