python2.4 or higher
pygtk2.6 or higher
pysqlite2 (if you have python 2.5, you already have this)
Note to packagers Gajim is a GTK+ app that loves GNOME. You can do 'make' so you don't require gnomepythonextras (aka gnome-python-desktop) which is gnome dep, but you will miss gnomekeyring integration.
Optional Runtime Requirements
For zeroconf (bonjour), the "enable link-local messaging" checkbox, you need dbus-glib, python-avahi
dnsutils (or whatever package provides the nslookup binary) for SRV support; if you don't know what that is, you don't need it
gtkspell and aspell-LANG where lang is your locale eg. en, fr etc
GnomePythonExtras 2.10 or above (aka gnome-python-desktop) so you can avoid compiling trayicon and gtkspell
gnome-python-desktop (for GnomeKeyring support)
notification-daemon or notify-python (and D-Bus) to get cooler popups
D-Bus running to have gajim-remote working
Some distributions also split too much python standard library. I know SUSE does. In such distros you also need python-xml the xml lib that *comes* with python and not pyxml or whatever.