The MAC is there to detect alteration of the data you are interested in, i.e. the result of the decryption. So you have the following choice:
- either you compute HMAC over the plaintext data (i.e. before encryption when encrypting, after decryption when decrypting);
- or you compute the HMAC over the encrypted data itself (i.e. after encryption when encrypting, before decryption when decrypting).
In the second case, you have to include in the HMAC input everything that impacts the decryption process, i.e. not only the encryption result per se, but also the IV which was used for that encryption, and, if the overall protocol supports algorithm agility, you should also input the specification of the encryption algorithm (otherwise, an attacker could alter the header of your message to replace the tag which says "AES-256" with the tag which says "AES-128" and you would unknowingly decrypt with the wrong algorithm).
For security, the second choice (encrypt then MAC) is better; see this question on crypto.SE for details (to sum up, when the MAC is computed over the encrypted data, it cannot leak information about the plaintext data, and since it is verified before attempting decryption, it protects against chosen ciphertext attacks). SSL uses MAC-then-encrypt and it has been the source of a lot of issues (all the "padding oracle attacks" and also the so-called BEAST attack would have been avoided with encrypt-then-MAC).
As for the keys, ideally, the encryption key and the MAC key should be derived from a master key with a PRF. In plain words: hash your master key K with SHA-512; the first half of the result will be the encryption key, the second half will be the key for HMAC.
But, really, you should use EAX or GCM. They do everything correctly and (that's an important point) they have very light requirements on IV selection: they just need a non-repeating IV, hence can use a simple counter, whereas handmade CTR needs non-overlapping IV ranges (an IV with uniform random selection is correct, but randomness is a hard requirement)(and CBC is even worse, it needs unpredictable randomness). The only justification for not using EAX or GCM in a new system (where you are not constrained with backward compatibility) is a possibly non-availability of an EAX or GCM implementation. I would argue that, even in this case, it would be better to retrofit some AES-ECB code into an EAX implementation.