This will be a post expanding as new knowledge is gained. I am in the process of installing ns-3.9 on a version of Ubuntu 10.10 already running ns-2.34, and with a Python run-time module installed, so this is not a post covering all potential errors that users installing on a clean version of Ubuntu may encounter.

First, after downloading the ns-allinone-3.9 code, the build process is started with If an error such as the one below occurs:
In file included from debug/bindings/python/
debug/bindings/python/pch/ns3module.h:3:20: error: Python.h: No such file or directory

install the Python development kit:
sudo apt-get install python-dev
Taken from here.