There are no specific requirements for the choice of cipher and MAC in the Encrypt-then-MAC construction, except that both should individually achieve their respective security goals (typically semantic security and existential unforgeability).
Indeed, this is the major advantage of Encrypt-then-MAC over other constructions like MAC-then-Encrypt or Encrypt-and-MAC, which do require the cipher and MAC to satisfy additional properties in order to be secure. (For example, Encrypt-and-MAC may be horribly insecure if the MAC leaks information about the plaintext.)
The MAC may be, and usually is, transmitted alongside the ciphertext, often appended to it. If the MAC is of a type that requires a nonce input, this will also need to be sent alongside it. Using the Encrypt-then-MAC construction ensures that this leaks no information about the plaintext, even if the MAC is not privacy-preserving, since the MAC is computer over the ciphertext.
As for the choice of MAC, I agree with Alex Gaynor's suggestion of using HMAC as the default choice, if there's no specific need to use some other MAC. The main advantages of HMAC are that it's easy to use, requires no nonce, and is provably (assuming that the hash function used satisfies the necessary assumptions) secure and privacy-preserving (and, in fact, a PRF).
That said, there are sometimes reasons to choose other MACs. For example, HMAC requires a cryptographic hash function, whereas CMAC can be implemented using just a block cipher (which you're probably already using for encryption), which can make it more convenient for constrained platforms like embedded systems. Meanwhile, polynomial-evaluation MACs like UMAC / VMAC or Poly1305 can be extremely fast, but require a dedicated implementation and the use of a nonce.