How does a client verify a server certificate? As far as I know,
when I request a certificate from Verisign (for example), and after they approved that I is me, they create a certificate (for me) that contains the digital signature and public key.
The digital signature is data that was created (not encrypted!) by their private key over my certificate data.
Now, a client connects to my site (which has an SSL certificate).

He reads the digital signature (from the certificate)
He knows which  algorithm used to create this signature, and he runs the hash again over my certificate data
Client uses his public key (in his store) of Verisign to decode (not  decrypt) the digital signature
If there is a match - all fine.
Client generates a random number, encrypts it with my public key, and my server accepts it and from now on - we are in symmetric mode.

I have the following questions:

Was I right?

Verisign creates the digital signature over my certificate data - which data?

The digital signature was created by what operation(?) over my certificate data? (Is this hashing?)


(I am not a cryptographer, but a  programmer who wants to understand this stuff.)
Was I right?
  


Pretty much. I want to add something to help clarify though: The Verisign public key in his store is of the Verisign CA (It is also stored in the form of a certificate). Also I think this process would qualify at decryption, no?


  
  Verisign creates the digital signature over my certificate data. Which data?
  


I'm not really sure what you mean here, but I'm guessing you are referred to the public keys store.

Basically the browser/OS have to trust a Certificate Authority (in this case Verisign). This trust is implemented by putting Verisign certificate including a public key inside the software. The corresponding private key will then be used to digitally sign certificates of websites that buy Verisign services. Because the browser have the public key, it can verify anything that Verisign signed using the corresponding key, hence the strength of this model.

A question might pop: Whose private key is then used to sign the certificate that is stored in the browser? It is usually self-signed (Use the very corresponding private key) or sign by a public key that is eventually self-signed. There is no way to verify self-signed certificate, hence the trust must be made in advance (by putting certificates in store).


  
  The digital signature was created by what operation(?) over my certificate data? (Is this hashing?)
  


What Verisign (and other CA) do is generated a private/public key pair (this process is called key ceremony). They then sign certificates of websites using the private key (Which is only done once per website), this process create a certificate that is signed by Verisign, which is then passed to the browser. If you're asking about the algorithms, basically they hash the certificate content and then encrypt the hash with the private key, so typically there's usually 2 algorithms used, one for hashing (MD5, SHA, etc.) and one for encryption (RSA, DSA, etc.)

Edit: Read comments to find out more, but I think basically this explanation is correct.