(This is the story as I heard it and learned it in the past. It may or may not be actually accurate, but then a lot of Unix history is passed around as folklore, and in some ways the folklore is more important and more influential than the truth.)

In the beginning, in V7, the Bourne shell didn't actually have comments. Instead, all it had was :, which is not quite a comment (you can see this for yourself in the V7 sh manpage). As part of V7's minimalism, the kernel had no mechanism to execute shell scripts; instead, the shell did that itself when the kernel's exec() refused to run an executable file.

When people at Berkeley created csh they gave it actual comments, introduced by # characters. Having two shells created a dilemma, though; when csh went to run a shell script, how would it know which shell the script was written for? The solution was simple. Since the Bourne shell didn't have # comments, csh could look at the start of the file; if it had a #, it was a csh script, and otherwise it was a Bourne shell script.

(Hence you at least used to be able to find some very, very old Bourne shell scripts that started ': this is a sh script' or the like.)

Shortly after that the people at UCB came to their senses and invented '#!', which makes the kernel exec() mechanisms directly handle shell scripts. In order to make Bourne shell scripts compatible with this new mechanism, BSD added support for # comments to the Bourne shell. For backwards compatibility, they left support for the old 'executed directly by the shell when exec() fails' form of shell scripts in both csh and sh, complete with csh's special peeking for '#' and ':' (where it lingers on even today).

I am not sure when # made it into the System V version of the Bourne shell, although I think that it didn't take too long, possibly because it was seen as a generally sensible idea given :'s defects as a general comment mechanism.

(I believe that kernel support for '#!' took much longer and thus you couldn't use a shell script as a user login shell on System V machines for quite a while.)

Sidebar: an amusing experiment

Put the following in an executable file and try to run it from within various shells (with eg 'sh -c /tmp/exper') on various systems:

#
for i in 1; do
  echo bourne-like shell
done

Now, change the first line from '#' to ':' and try the experiment again.

(This is not the only example of Unix fossilization.)