Protocols

SIP is the main standard, and is open. Different SIP clients can work together, however due to codecs differences and other aspects, this may 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.
Also, applications under VirtualBox seem to have more firewall related problems, even when using bridged mode.

SIP

You cannot seem to have two applications registered to the same SIP account at the same time (it probably depends on the server settings, of course). Note that Ekiga does not unregister its session when quitting (you have to manually do it in the Accounts window).
An outbound proxy is the server used to make outgoing calls.
The best codec seems to be G711 (u-law / A-law).

On Linux the best application seems to be Ekiga. On version 3.2 it has decent video and audio quality, and a nice interface. It seems to be very buggy though.
Other worthy applications:
- sflphone
- twinkle (seems way stabler than Ekiga for audio calls)
- qutecom (very buggy right now, but nice interface)
- SIP Communicator (written in Java, currently totally unusable on Gentoo, but maybe interesting later).
- Linphone (most of the times, does not work)
- Empathy (could not get SIP to work, and is a typical Gnome application, eg, very bad :)

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.

To get debugging ouput under Gentoo, Ekiga and associated libraries must be built with the debug USE flag (that's not only for internal gdb debugging).
To get DTMF support (the ability to send tones via the dialpad), you must build Ekiga and its libraries with the dtmf USE flag. It does not seem to work very well (with every system) yet though. If you press a key on the dialpad while Ekiga was not built with DTMF, I had a very strange error (every call would later result in "Security Check Failed"). The error goes away after some time.

Twinkle is still based on Qt 3, and has such is ugly and currently have a problem with KDE 4 preventing the application from minimizing to the system tray.
Apart from that, it looks more mature than Ekiga. I had fewer problems when calling via Localphone.com VoIP provider (calls are getting disconnected though).
It is now masked in Portage so is not a long term solution unless a new version (KDE 4 native) appears.

For conferences (eg, more than 2 people) a server should be used, with each peer obtaining a connection to the server.

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.