At the time of writing this post the Debian package on NLTK download page is built for Python 2.5. Ubuntu ships with Python 2.6 by default. So you need to download the source package from the NLTK download page.
NLTK needs some dependency modules, lets install them.
sudo apt-get install python-numpy python-matplotlib prover9
Uncompress the source package and run the NLTK setup.
$ unzip nltk-2.0b3.zip
$ cd nltk-2.0b3/
$ ls build LICENSE.txt nltk PKG-INFO README.txt setup.py yaml
$ sudo python setup.py install
After finishing the NLTK setup, you should download the NLTK data which contains various corpora, tagsets and treebank data etc.
Python 2.6.2+ (release26-maint, Jun 19 2009, 15:14:35)
[GCC 4.4.0] on linux2
Type “help”, “copyright”, “credits” or “license” for more information.
>>> import nltk