Why does the error message for two colons as a command (::) in bash have three colons, but a single colon give no output?

The last colon is just part of the default "not found" message:

$ x
x: command not found
$ ::
::: command not found

The reason a single colon produces nothing is that : is a valid command - although it does nothing (except return TRUE). From the SHELL BUILTIN COMMANDS section of man bash:

   : [arguments]
          No effect; the command does nothing beyond  expanding  arguments
          and  performing any specified redirections.  A zero exit code is
          returned.

You will sometimes see it in constructions like

while :
do
  something
done

See for example What purpose does the colon builtin serve?

The : shell built-in vs non-existent ::

The : shell built-in command exists (note the difference between external and built-in commands) which does nothing; it just returns success, just like the true command. The : built-in is standard and defined by the POSIX standard, where it's also known as the "null utility". It is frequently used for testing or for running infinite loops as in while : ; do ...;done

bash-4.3$ type :
: is a shell builtin

However, :: - two colon characters together - are interpreted as one "word" to the shell, and it assumes to be a command the user entered. The shell will go through the process of checking built-ins, then any directory in the PATH variable for existence of that command. But there is neither a built-in :: nor external command ::. Therefore, that produces an error.

Well, what is a typical format for an error?

<shell>: <command user typed>: error message

Thus, what you see isn't 3 colons but what you typed pasted into the standard error format.

Note also, that : can take command-line arguments, i.e. it is legal to do:

: :

In this case, the shell will consider that as two "words", one of which is a command and the other a positional parameter. That will also produce no error! (See also the historical note (later in this answer) about the use the of : with positional parameters.)

In shells other than bash

Note that formatting can vary between different shells as well. For bash, ksh, and mksh the behavior is consistent. For instance, Ubuntu's default /bin/sh shell (which is actually /bin/dash):

$ dash
$ ::
dash: 1: ::: not found

where 1 is the command number (equivalent to the line number in a script).

csh by contrast produces no error message at all:

$ csh
% ::
%

In fact, if you run strace -o csh.trace csh -c ::, the trace output in csh.trace file reveals that csh exits with exit status 0 (no errors). But tcsh does output the error (without outputting its name, though):

$ tcsh
localhost:~> ::
::: Command not found.

Error messages

In general, the first item in the error message should be the executing process or function (your shell tries to execute ::, hence the error message comes from the shell). For instance, here the executing process is stat:

$ stat noexist
stat: cannot stat 'noexist': No such file or directory

In fact, POSIX defines the perror() function, which according to the documentation takes a string argument, then outputs error message after colon, and then newline. Quote:

The perror() function shall map the error number accessed through the symbol errno to a language-dependent error message, which shall be written to the standard error stream as follows:

• First (if s is not a null pointer and the character pointed to by s is not the null byte), the string pointed to by s followed by a colon and a <space>.

• Then an error message string followed by a <newline>.

And the string argument to perror() technically could be anything, but of course for clarity it's typically the function name or argv[0].

By contrast, GNU has its own set of functions and variables for error handling, which a programmer can use with fprintf() to stderr stream. As one of the examples on the linked page shows, something like this could be done:

  fprintf (stderr, "%s: Couldn't open file %s; %s\n",
           program_invocation_short_name, name, strerror (errno));

Historical note

In old Unix and Thompson shell, : was used with goto statement (which according to user named Perderabo on this thread wasn't a shell built-in). Quote from the manual:

The entire command file is searched for a line beginning with a : as the first non-blank character, followed by one or more blanks, and then the label. If such a line is found, goto repositions the command-file offset to the line after the label and exits. This causes the shell to transfer to the labelled line.

So you could do something like this to make an infinite loop script:

: repeat
echo "Hello World"
goto repeat

Try any other non-existent command and you'll see that the : serves its normal purpose in English:

$ ---
---: command not found