The choice between NIS and NIS+ is easy - use NIS if you don't have to use NIS+ or have severe security needs. NIS+ is _much_ more problematic to administer (it's pretty easy to handle on the client side, but the server side is horrible). Another problem is that the support for NIS+ under Linux is still under developement - you need the latest glibc snapshot for it or have to wait for glibc 2.1. There is a port of the glibc NIS+ support for libc5 as drop in replacement.
The choice between "traditional NIS" or the NIS code in the NYS library is a choice between laziness and maturity vs. flexibility and love of adventure.
The "traditional NIS" code is in the standard C library and has been around longer and sometimes suffers from it's age and slight inflexibility.
The NIS code in the NYS library requires you to recompile the libc library to include the NYS code into the libc library (or maybe you can go get a precompiled version of libc from someone who has already done it).
Another difference is that the traditional NIS code has some support for NIS Netgroups, which the NYS code doesn't. On the other hand the NYS code allows you to handle Shadow Passwords in a transparent way. The "traditonal NIS" code doesn't support Shadow Passwords over NIS.
Forgot this all if you use the new GNU C Library 2.x (aka libc6). It has real NSS (name switch service) support, which makes it very flexible, and contains support for the following NIS/NIS+ maps: aliases, ethers, group, hosts, netgroups, networks, protocols, publickey, passwd, rpc, services and shadow. The GNU C Library has no problems with shadow passwords over NIS.