When using NFS without kerberos the security of all data in the NFS share depends on the integrity of all clients and the security of the network connections. If you use kerberos the security doesn't depend on all client machines because the server gives access to users with a valid kerberos ticket only. The security isn't completely delegated to the client machines (unlike without kerberos). Therefore you need a principal in your kerberos realm for each user who want's to access the NFS share. See Kerberos in the Ubuntu Server Guide on this topic. The section "Kerberos Linux Client" applies also to Ubuntu 8.04.
You need a working Kerberos (MIT or Heimdal) KDC (Key Distribution Center) before continuing. NFS4 and Kerberos work fine with Ubuntu 8.04; they do not seem to work with the (much) older Ubuntu 6.06, or at least I couldn't get Heimdal to work correctly.
Please note, that we have three different entities: the Kerberos-server; the NFS-server and the NFS-client. Your Kerberos-server (or KDC) and NFS-server could be the same machine, but they could also very well be separate entities. We will use separate "prompts" to distinguish, i.e. if you see
KDC$ echo "hello"
... this means you need to type echo "hello" on the KDC.
Please note that you can now (with Ubuntu 8.04 and later) use any encryption type you want, there is no more need to extract only des-cbc-crc, as most sites suggest. See [http://mailman.mit.edu/pipermail/kerberos/2008-May/013698.html this mailinglist message].
Please also note, that des-cbc-crc encryption is depreciated and, starting with Ubuntu 10.04, is no longer supported by default in the Kerberos libraries. For nfs4 to work, you need to add allow_weak_crypto = true to /etc/krb5.conf
On the nfs-server and nfs-client you need at least the krb5-user and optional libpam-krb5 if you wish to authenticate against krb5.
# apt-get install krb5-user # apt-get install libpam-krb5
On the nfs-server and nfs-client you need heimdal-clients and optional libpam-krb5 if you wish to authenticate against krb5.
# apt-get install heimdal-clients # apt-get install libpam-krb5
# modprobe rpcsec_gss_krb5
Add rpcsec_gss_krb5 to /etc/modules to have it loaded automatically. (I'm pretty sure they're loaded automatically though).