The two major protocols used for VoIP are SIP and H.323. (They are completely different standards, not related to each other). SIP isn't so much a complete VoIP protocol - other protocols are required for the actual voice data transmission. See the SIP page for more details.
See http://voip.fast.co.nz , a NZ voip PABX you can connect to and make free calls.
The New Zealand Dialplan is available on the Number Administration Deed website http://www.nad.org.nz (Note that there are conflicts between the 2 documents published on their website)
http://www.openh323.org/ GnuGK and friends make up the openh323 project. GK is an h.323 gatekeeper (central server thing).
A more 'hardcore' SIP server. Less features, more commercial. SIP supports textual messaging, so SER has a Jabber gateway.
Very easy to use, free for personal use and actually works quite well (And Windows versions also) Alas, no presence (i.e. no IM (sigh))
SIP (TCP Only), H.323, etc. Nice and integrated.
SIP based IP PBX - currently Windows, Linux version planned for 2007
Clients can be connected to more than one service at a time, think of it as having 2 separate phone lines, both connected to different providers but both phones plugging into one unit.. so feel free to sign up for accounts at more than one service.. you can select which service you want when dialling away from the default service by starting to dial your numbers with #2 for the second account you have setup etc.
SIP is the new protocol used to initiate communication between various units, and it is a standard met by clients on Linux, Windows, or on stand-alone VoIP phones. This means you can call any user on the network not caring what kind of hardware they are using, the SIP should help start a common conversation so you can talk to each other.
To try it out, get yourself a client from the links listed at the top of this page, if you find any other clients please add them to this list, or if you want to point out problems or good points add them to this list also. Then register with a service listed on the SipServices page.
If you have a public IP address with the right ports unfirewalled, people can also connect directly using asip://firstname.lastname@example.org URI.