Theoretically, what if I were to change some magic numbers in, say, AES?
How are these (magic) numbers chosen?


It heavily depends on what algorithm and which of its magic numbers. They seldom are entirely arbitrary. In AES, it is often taken the lowest value such that a certain mathematical property holds, with that property (demonstrably or plausibly) working towards security. In other algorithms, it could be values that pre-existed in another context (like mathematical constants), often screened so that some criteria is met (e.g. being odd).


  Are they chosen 'manually'?


Quite often so. Or, as is the case in AES S-boxes, an auxiliary program is used.


  I could theoretically pad the encrypted message with them and 'load' these tables with the numbers before the algorithm is kicked off to encrypt/decrypt, right?


Yes.


  Then why have these numbers as constants in the algorithm?


Occam's razor. And other good reasons, among which:


Introducing parameters rather than constants, especially along messages, could very realistically open to attack. For example, if AES S-boxes where a parameter prefixed to a short AES-GCM message, an attacker could change a bit in these constants in the prefix and see if the message gets nevertheless accepted by the receiver despite that change, meaning with high likelihood that the particular S-box entry for this bit was not active during decryption, which would reveal a lot of information about message and key. That could allow recovery of message and key with a realistic number of attempted decryptions.
Changing constants to variables would make hardware implementations slower, larger, more power-hungry and complex. In the case of AES, the standard constants are carved into modern CPUs.
Changing constants may invalidate complex optimizations (for speed or side-channel leakage) that went into translating the constants to hardware or software. In the case of AES S-boxes, see e.g. Joan Boyar and René Peralta: A Small Depth-16 Circuit for the AES S-Box, in proceedings of SEC 2012.



  You could even consider the table(s) of magic numbers used a sort of "extra key"


There are better ways to obtain that. For example, what's fed to the key input of AES could be obtained with a Key Derivation Function applied to the normal key and extra key.