Validation is about making sure that a certificate is genuine. The goal is to know whether the public key you see is really owned by the server you intend to talk to. This validation entails a lot of steps, described there in all their gory details; most of them are completely local to the client machine, so you won't see them show up in any way with network traces. In fact that's the whole idea of certificates: to allow offline validation.
There is still one step of certificate validation which cannot be really offline, which is the check for the revocation status. By definition, revocation is about cancelling a certificate that otherwise looks fine. The three main methods for ascertaining revocation status are:
CRL: a list of revoked certificate is regularly published by the CA (or another entity to which that power was delegated). The CRL is signed, and valid for some time (a few hours or days).
OCSP: an duly designated OCSP server can be asked for the current status of a certificate. The OCSP response is signed, and has its own validity dates, so an OCSP response is somehow equivalent to a CRL that talks about a single certificate.
Nothing: for a very long time, Web browsers simply assumed that no certificate was ever revoked, which sure makes the implementation much simpler.
URL for CRL download or for talking to an OCSP server are written in the certificate itself. A system that wants to validate a certificate (your Web browser; a "relying party" in X.509 terminology), and does not use the "nothing" method of revocation check, will want to download a fresh CRL or obtain a fresh OCSP response. However, it may also cache the obtained CRL or OCSP response; Windows, in particular, maintains a CRL cache that is resistant across reboots. Thus, if the browser downloads a CRL, you will see the CRL download on your network traces only once per day or so (depending on the CRL nextUpdate field). You can inspect the Windows CRL cache with certutil -URLcache CRL. Note that Firefox does its own validation completely independently of the Windows support for certificates.
OCSP stapling is an SSL/TLS extension by which a client may ask the server to send, as a CertificateStatus message, an OCSP response that establishes that the server certificate is not revoked (for now): since OCSP responses are dated and signed, how such a response is obtained has no importance. Since the server can reasonably assume that all clients that talk to it will need the verify the revocation status of the certificate that the server sends, it makes sense to use the server itself as a cache for the relevant OCSP response. It avoids the need for the client to open an extra connection to the OCSP responder, and it makes life easier for the OCSP responder too, because it just have to sign a single fresh response once every few hours.
Not all servers support OCSP stapling, which is why you won't see CertificateStatus messages for all servers.
