NFS kernel-server

# apt-get install nfs-kernel-server

If you like me use a firewall between the networks, you need to configure NFS to use pre-defined ports (or atleast should cause it makes your life more easy), as opposed to having portmapper deciding dynamically.

Edit /etc/default/nfs-kernel-server (only showing what I have changed, I choose to beef up RCNFSDCOUNT from 8 to 32 as I have 40 machines mounting the same export):
RPCNFSDCOUNT=32
RPCMOUNTDOPTS="--port 4002"

Edit /etc/default/nfs-common:
STATDOPTS="--port 4000 --outgoing-port 4001"

Restart both nfs-kernel-server and nfs-common. Note that all clients need to have the same ports setup.

Open:
TCP ports 111, 2049, 4000 & 4002.
UDP ports 111, 794, 2049, 4000 & 4002.

Check the nfs-server from a client with rpcinfo:

# rpcinfo -p program vers proto port
100000 2 tcp 111 portmapper
391002 2 tcp 705 sgi_fam
100000 2 udp 111 portmapper
100024 1 udp 4000 status
100024 1 tcp 4000 status
100003 2 udp 2049 nfs
100003 3 udp 2049 nfs
100003 4 udp 2049 nfs
100021 1 udp 58452 nlockmgr
100021 3 udp 58452 nlockmgr
100021 4 udp 58452 nlockmgr
100003 2 tcp 2049 nfs
100003 3 tcp 2049 nfs
100003 4 tcp 2049 nfs
100021 1 tcp 38677 nlockmgr
100021 3 tcp 38677 nlockmgr
100021 4 tcp 38677 nlockmgr
100005 1 udp 4002 mountd
100005 1 tcp 4002 mountd
100005 2 udp 4002 mountd
100005 2 tcp 4002 mountd
100005 3 udp 4002 mountd
100005 3 tcp 4002 mountd

Now just setup some exports in /etc/exports and run exportfs and mount it, don't forget to add the shares to fstab for mounts upon boot!