I'd imagine the process works something like this:

   * Generate the new key
   * Sign the new key with the old key
   * Generate the revocation cert for the old key
   * Push the revocation publicly with a reason of "Superseded by (fingerprint of new key)" or similar
   * Push the new key
   * Try to get your new key signed by everyone that signed your old key for authenticity's sake

I'm not too sure how the community of GPG users out there sees key revocation socially, so you may or may not want to bother with that bit. Perhaps hold off on pushing the revocation until the new key has been in use for a while?