How does ssh public key authentication work?

In brief:

• SSHv1: The server encrypts a message using a public key stored in authorized_keys, the client has to decrypt it and return it's checksum (modified by a session ID)
• SSHv2: The client signs a message (depending on the session ID) and transmits the signature and message (without the session ID) including the public key used. The server then prepends the session ID and verifies the signature (provided the public key is actually in authorized_keys)

The document PROTOCOL.agent summarizes this:

Protocol 1 and protocol 2 keys are separated because of the differing cryptographic usage: protocol 1 private RSA keys are used to decrypt challenges that were encrypted with the corresponding public key, whereas protocol 2 RSA private keys are used to sign challenges with a private key for verification with the corresponding public key. It is considered unsound practice to use the same key for signing and encryption.

Here's the SSHv2 relevant section from RFC 4252:

To perform actual authentication, the client MAY then send a
signature generated using the private key. The client MAY send the
signature directly without first verifying whether the key is
acceptable. The signature is sent using the following packet:

  byte      SSH_MSG_USERAUTH_REQUEST
  string    user name
  string    service name
  string    "publickey"
  boolean   TRUE
  string    public key algorithm name
  string    public key to be used for authentication
  string    signature

The value of 'signature' is a signature by the corresponding private key over the following data, in the following order:

  string    session identifier
  byte      SSH_MSG_USERAUTH_REQUEST
  string    user name
  string    service name
  string    "publickey"
  boolean   TRUE
  string    public key algorithm name
  string    public key to be used for authentication

When the server receives this message, it MUST check whether the
supplied key is acceptable for authentication, and if so, it MUST
check whether the signature is correct.

The particulars of the authentication depend on the protocol version and the type of key. In all cases, there is always a challenge, with some randomness to avoid replay attacks. When the user key is of type DSA, a true digital signature is necessarily involved, since DSA is a signature-only algorithm. The article you link to shows something which assumes that the user key can do asymmetric encryption; I guess this is something that SSHv1 did (in SSHv1, all keys were RSA, and RSA can do asymmetric encryption). For the current (SSHv2) protocol, public-key based client authentication is specified in RFC 4252, section 7.

The core concept remains the same: the client proves its control of the private key by performing an operation which requires knowledge of that key, but such that the "inverse" operation can be done with the public key which is located in the .ssh/authorized_keys on the server.