There is a Novell book on Firewalls which may be better to use than the 2.4 based Howto. I don't know if there is a newer version of that particular howto. There are iptables howto's that may have a section on masquerading. The changes from ip_conntrack to nf_conntrack for example is very resent. Earlier 2.6 kernels used ip_conntrack. If you modprobe nf_contrack, and then look at lsmod, you will probably see other modules loaded as well. Just modprobe it and use the lsmod results. You will most likely find that you have the modules you need and don't need to recompile your kernel.

What kind of documentation comes with Ubuntu, because I thought it was supposed to be a user friendly distro. I bet that you simply overlooked something in the docs or a config wizard that would make things easier for you.

I don't have an Ubuntu server installed. You might try their wiki, because NATing an internet connection is usually something you can setup from any distro's firewall or network config wizards without having to become an expert in designing firewalls on your own. If they don't you could try a different distro or buy a NAT router.