The difference between MAC algorithms and what to use I've been looking into message authentication codes and found several ways to create integrity for a message. I know of the following algorithms:

HMAC, this can use any cryptograhpic hash function and a key, for a HMAC to be secure the underlying hash function does not have to be (though I assume it would be a good thing to not use broken hash functions just for the sake of good practice) I also understand it is better not to use the same key for encryption and HMAC but to use a different key for both.

GCM, GCM is a mode operation for symmetric encryption ciphers. The benefit of this is that the key you encrypt with, also does the authentication.

CBC-MAC is a MAC based on the mode operation CBC, conterary to what i first thought you first encrypt the text with (for example) AES-CBC and then apply the CBC-MAC (If using encrypt then mac) and it is not the CBC mode for encryption with authentication.

I believe the best thing to do is encrypt then MAC as explained here

What i would like to know (given I'm working with data over internet): what is the best algorithm to provide integrity and did I miss any well-know-good-to-use algorithm.

Also, I've seen these terms used interchangeably but authentication is something different than integrity right? authentication is verifying the sender (PKI) and integrity is verifying the received data (MAC). but then why is it message authentication, i know an other word for it is MIC (which seems better to me) but is used in WPA (when MAC has an other meaning). Could someone be so kind as to explain the terminology as well?
First the theoretical explanations:


Integrity and authenticity are different goals to achieve, but both are achieved (for symmetric encryption) with a MAC.
You should probably be using encrypt-than-MAC or an authenticated cipher unless you have very good reasons not to. No blanket statements can be made though.




HMAC: HMAC is a often used construct. It is recommended to use a separate key for the HMAC but you may get away with using the same key as used for encryption as I haven't heard of any attacks that could attack a scheme with one key for HMAC (but if anybody switches it to CBC-MAC you're in trouble). HMAC, as noted, relies on a hash. A hash function could either be faster or slower than a cipher.

GCM: GCM is an AEAD cipher that has very good performance on (Intel) 32 / 64 bit processors, especially if hardware support can be utilized. As it uses the GMAC construct it may be faster than performing a separate MAC function. It's also pretty easy to use, but it may be hard to get right on embedded systems. Because of the speed it's also known as a 1.5 pass authenticated cipher (as in: the data is processed 1.5 times, 1 time for encryption and 0.5 times for authentication/integrity).

CBC-MAC: is an insecure construct that uses a block cipher (usually the one also used for encryption, of course). There are attacks on CBC-MAC, it should only be used on data of known length and you should use a separate key.



There are other MAC constructs, notably:


CMAC which is basically a fix for the length-related deficiency of CBC-MAC
Poly1305-AES - which is often combined with one of the stream ciphers from Daniel J. Bernstein


And there are many AEAD ciphers as well:


OCB mode (multiple versions) a patented single pass mode, very efficient
CCM mode, a packet based AEAD cipher that uses a 128 bit block cipher with fun peculiarities
EAX an AEAD cipher that uses a 128 bit block cipher, brought up as a candidate to replace CCM at NIST because of the fun peculiarities


MAC algorithms alone are not authenticated ciphers, so if you need encrypt as well, you'll have to specify your own protocol on how to do this. There are efforts to create an authenticated cipher (AEAD cipher) out of CBC and HMAC. Basically EAX mode has done the same with CTR and CMAC. Don't include the IV in the calculation. AEAD ciphers will automatically include it.



Finally note that AEAD ciphers are very much a topic of research.



There's a lot more to be said about MAC algorithms and AEAD, but this is as broad as I would like to go.