[y0ghur7_xxx]

can't an observer possibly encrypt many possible and likely short messages (like, "hey!" or "lol") with the public keys of some users of value and sniff the network for matches?

no. the same message does "never" encrypt to the same cypher:

    $ echo lol | gpg -e -r F8669BB7 --armor
    -----BEGIN PGP MESSAGE-----
    Version: GnuPG v1.4.11 (GNU/Linux)
    
    hQEMA2gTLr1USDZGAQf/YbbnzHvNfdqbs6hmdmIaaiZOSfW9P6Bc8tdF4MG/JbP+
    RTxbLpi4W+vXs+WrD9jdik8KuDdZV54O1mb6Ido3xrYeEPBo0Vje2eVpgUy01VUa
    2RM76NvsX1VN9rap6KvHuO/h7IFwDuAtvUUcDyFH+qK2UEHordFi+mWKqICocQt0
    WWgpCk5BVgM/1q2c2ruWxVuZs/IMh9LQGZ1i7hpkJHAYqovhghROmGarUuJYXGDi
    s6rSMpjxbXDhPMYbbhbBI4pRhgKtN2FMlKyI3XoH+LCFHsOyBmazroVYWFu+gafH
    6LU2Z65OQyJWqX5CLdwab4qpUQdht6lqkUHRJB9xdtI/AfTFF7BbRP8PR+q9GVAe
    r4I812VmBn3hwBHJzNiFDEGVkt/IDpd6M/X2Vi0xJx0LUaICL+swPVudenPuvlnt
    =zeUd
    -----END PGP MESSAGE-----
    
    
    
    $ echo lol | gpg -e -r F8669BB7 --armor
    -----BEGIN PGP MESSAGE-----
    Version: GnuPG v1.4.11 (GNU/Linux)
    
    hQEMA2gTLr1USDZGAQgAo4ZEHGWKSgwVmbC7crACvTXVtlgP4n8J/3oSohct9zrM
    SqPd4L5TWsjOh+2LlG7WQbPnpn4Tcv9c4RyPNb+1C/fWRmGhV+a3QhuC+rrus5c6
    /FPwsHTjO30N0AnCMzoXAaqDRRGw859BKazEZyxIHherU+o7wNRKrW6U1ikRd/Pu
    BwHChUZHBRmZhomrtYPbQ5cNAJQtPMj94Z8OuZeCEzPNBr3opevoMs2j+9ysOtkF
    7Cam3jTKLM3GwHSm4c7WzhdJJsXbnOn8ODYRBf++4oJChPIqeT2EssigAQuuhHlk
    pDhM40zB7hAd6MJM52cZpM3UqTe/iI4vHSrQ+pw/otI/AWY6s4aIlF5AAzoM0wAR
    FzobJ5Vbp7fBgA1SiOhEhSAdT/U2yy2jQcQN53yyX9Vqtunh3dNmCGaNNavszK8+
    =YDLc
    -----END PGP MESSAGE-----
    $

[IanCal]

As someone who doesn't know the structure of the output, what's the significance of:

    hQEMA2gTLr1USDZGAQ

At the start of each output? Is that 'lol' encrypted then followed by random bytes, or does it contain header information?

[Zash]

It's a header with a version number and the ID of the receivers key that the message was encrypted with. Base64-decode and hexdump those messages and look for 54483646 (one of the subkeys of F8669BB7). The encrypted message is after that and would look random. The format is defined in http://tools.ietf.org/html/rfc4880

edit: It's not encrypted with the primary key, but one of the subkeys.

[IanCal]

Interesting, thanks for the overview. I'll have a poke around the doc :) I've been meaning to look into more about how these things work. I understand the very high level stuff and the very low level (how to use the tools roughly and some of the maths behind it all) but not so much in-between.