Protocols

SIP is the main standard, and is open. Different SIP clients can work together, however due to codecs differences and other aspects, this can not always work. SIP is more modern than H323 (an older standard) and is probably the best choice right now (March 2009).
Work is in progress to add VoIP (audio / video support) to the XMPP (Jabber) protocol through the Jingle project.
A SIP account can be obtained for free at ekiga.net. Note that Free gives you a SIP account (freephonie.net), however they do not always obey to the SIP specifications and some clients cannot work with this account. On the other hand, other clients have trouble connecting to ekiga.net...
Firewalls can be problematic so some applications will use a STUN server to work around NAT issues. Ekiga seems to work fine, other applications are not always able to do this correctly apparently.

Applications

On Linux the best application seems to be Ekiga. On version 3.2 it has decent video and audio quality, and a nice interface.
Other worthy applications:
- qutecom (very buggy right now, but nice interface)
- SIP Communicator (written in Java, currently totally unusable on Gentoo, but maybe interesting later).
- Linphone (somehow works, sometimes)

On Mac OS X Ekiga is unfortunately not available. X-Meeting should be used but it seems much more buggy than Ekiga.
GoogleTalk will add support for SIP at some point.

There are many closed protocols and applications. Skype is one of them. It is easy to setup and works relatively well, but the Linux version is not the same quality as the Windows one.
MSN, iChat etc also use closed protocols which makes the use of audio / video hard with them.