Just a note I've done this mostly on Redhat so it may vary slightly by distro...
Some of the basic things that need to be configured:
/etc/sysconfig/network (may vary by distro) should have a line like so:
/etc/yp.conf should have a line like this:
domain <NIS_DOMAINNAME> broadcast
'domainname' should echo what your NIS_DOMAINNAME is set to.
/usr/lib/yp/ypinit -m #initiallizes NIS
after that you can check to see if it's running with these commands:
service ypserv status
service ypbind status
There are other options that you may want to change, configure, modify, etc. examples: /etc/ypserv.conf, /etc/nsswitch.conf, there are probably others
On the nodes it's similar,
check your domainname is correct
modify /etc/yp.conf should contain a line like this:
domain <NIS_DOMAINNAME> server <server_IP>
after all those things are done do 'service ypbind restart'
That should at least get a basic NIS server/client up and going...