What is the relationship between an OpenPGP key and its subkey?

About Primary Keys and Subkeys

The master key (like the private key) was used to sign data that only the subkey (the public key) could decrypt, but the subkey (the public key) could only encrypt data, which could then only be decrypted by the master key (the private key). Am I correct in this assumption, or are they 2 separate key-pairs altogether?

You haven't got the concepts of public/private key (also called assymetric) cryptography quite right. Each set of public and private keys is split, you publish the public key so others can use it and keep the private key private. Signatures issued by the private key can be verified through the public key, messsages encrypted using the public key can be decrypted with the private key. There is no immediate relationship between primary key and subkey pairs in OpenPGP, these are completely different key pairs.

Is it just GnuPG that uses this method, where a subkey is created automatically for encryption, or is this mandated by the OpenPGP protocol?

The default setup in GnuPG is you have a primary key pair used for certification and signatures, while the encryption subkey is used for encryption only. Using RSA, you could also generate primary keys supporting all those operations (and with GnuPG and the --expert flag, you can!). This is mostly because of other algorithms like DSA and Elgamal, which only support one of the operations (DSA is for signing only, Elgamal for encryption) where you need to have different keys.

There is also some advantage in having different keys for different usages: consider a flaw is found that allows to calculate a private key from signatures under certain conditions. While your signing key would be targeted, the encryption subkey is another one and not targeted by this attack. Some people even consider restricting the primary key to certification only and adding two subkey pairs is best practice, one for signing, one for encryption.

Binding Signatures

If they are 2 separate key-pairs, what mathematically binds the subkey to the master key?

In OpenPGP, a special kind of binding signature is issued when a subkey is created. Subkeys capable of signing can also issue such a binding signature on the primary key. Those special signature are defined in RFC 4880, OpenPGP, 5.2.1. Signature Types:

   0x18: Subkey Binding Signature
       This signature is a statement by the top-level signing key that
       indicates that it owns the subkey.  This signature is calculated
       directly on the primary key and subkey, and not on any User ID or
       other packets.  A signature that binds a signing subkey MUST have
       an Embedded Signature subpacket in this binding signature that
       contains a 0x19 signature made by the signing subkey on the
       primary key and subkey.

   0x19: Primary Key Binding Signature
       This signature is a statement by a signing subkey, indicating
       that it is owned by the primary key and subkey.  This signature
       is calculated the same way as a 0x18 signature: directly on the
       primary key and subkey, and not on any User ID or other packets.

Addressing Subkeys in GnuPG

When I upload a key to a keyserver, which key is uploaded, my master key or the subkey? Or both?

When I use the --export function, which OpenPGP key is exported when I specify my UID?

Usually, in GnuPG key IDs and UIDs are always resolved to the primary key. All export operations (and uploading to a keyserver is also considered an export) also export the subkeys, user IDs and certifications on your key. Similar things exist for other operations like signing and encrypting. If you really want to denote a subkey for operations, you have to add ! behind the subkey (eg. gpg --recipient 0xDEADBEEF! --encrypt).