How do programs like gitolite work?

gitolite in itself is an authorization layer which doesn't need ssh.
It only needs to know who is calling it, in order to authorize or not that person to do git commands.

SSH is used for authentication (but you can use an Http Apache for authentication as well, for instance)

The way gitolite is called by ssh is explained in "Gitolite and ssh", and uses the ssh mechanism forced command:

The ~/.ssh/authorized_keys (on the gitolite ssh server) looks like:

command="[path]/gitolite-shell sitaram",[more options] ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEA18S2t...
command="[path]/gitolite-shell usertwo",[more options] ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEArXtCT...

First, it finds out which of the public keys in this file match the incoming login. Once the match has been found, it will run the command given on that line; e.g., if I logged in, it would run [path]/gitolite-shell sitaram.
So the first thing to note is that such users do not get "shell access", which is good!

(forced command = no interactive shell session: it will only provide a restricted shell, executing only one script, always the same)

Before running the command, however, sshd sets up an environment variable called SSH_ORIGINAL_COMMAND which contains the actual git command that your workstation sent out.
This is the command that would have run if you did not have the command= part in the authorized keys file.

When gitolite-shell gets control, it looks at the first argument ("sitaram", "usertwo", etc) to determine who you are. It then looks at the SSH_ORIGINAL_COMMAND variable to find out which repository you want to access, and whether you're reading or writing.

Now that it has a user, repository, and access requested (read/write), gitolite looks at its config file, and either allows or rejects the request.

The fact that the authorized_keys calls a perl script (gitolite-shell) is because Gitolite is written in perl.
It could very well call a javascript program.

If your ssh on GitHub without any command, you get a greeting message, like your mention in your question.
Gitolite displays a similar message, as detailed in the print_version() function of the info command script:

sub print_version {
    chomp( my $hn = `hostname -s 2>/dev/null || hostname` );
    my $gv = substr( `git --version`, 12 );
    $ENV{GL_USER} or _die "GL_USER not set";
    print "hello $ENV{GL_USER}, this is " . ($ENV{USER} || "httpd") . "\@$hn running gitolite3 " . version() . " on git $gv\n";
}

The message looks like:

hello admin, this is git@server running gitolite3 v3.0-12-ge0ed141 on git 1.7.3.4

The late 2013 Gitolite documentation now includes that diagram which summarizes all the pieces:

Note that sshd does a linear scan of the ~/.ssh/authorized_keys file. Once you get about 3000 keys in there, people whose keys appear later in the file start to notice the lag -- it begins to be more than network lag :-)

That is one reason why github has their own patched version of sshd. They have far too many users to be able to manage with normal sshd!