There are numerous choices of wiki software. MediaWiki is the software used to power Wikipedia, which is very powerful and scalable, but the familiarity of the software tends to push users towards treating the wiki like an encyclopaedia. This may or may not be what you want.
This website used to run UseModWiki, which is a simple Perl wiki script. UseMod lacks many of the features provided by other wikis, and has received bugfixes only since 2003.
MoinMoin's wiki include a walkthrough for setting up a MoinMoin wiki under Ubuntu that is an excellent starting place.
Aside from the Desktop Edition, MoinMoin's tarball is actually an set of components for you to install, which may surprise those expecting to find a web application ready to run (like, for example, Wordpress).
MoinMoin's code can be installed to your Python site-packages directory, leaving a clean directory structure for the data and configuration, that would look something like this:
wikiconfig.py - the configuration for the wiki
moin.wsgi - a WSGI handler that is run by the webserver (with mod_wsgi)
data/ - The site's wiki pages and user accounts
As long as you have the privileges to run cgi-scripts on your server you can set up a wiki in a matter of minutes.
I'd recommend http://www.usemod.com (the script that this wiki uses). It's a tiny download that gives you a single perl script and one or two config files. Instructions are given in the download package INSTALL file.
At its simplest you can simply edit the perl script to set the url of your web space then upload it to your cgi-bin directory. A link to <your web space>/cgi-bin/wiki.pl gets you to an automatically generated home page and you're away! There are plenty of options to tweak but that's all it takes to get up and running.