How much you gain by starting threads is also determined by what you're doing in those threads. Remember (or learn): In CPython only one thread at a time can execute python code, so depending on your task threading might gain you little. If you're doing I/O or calling functions written in C (and if they release the Global Intepreter Lock [GIL]) you might gain a lot by using threads.
As for overhead: profile, profile, profile. You'll have to do sample runs and find your sweet-spot. It all depends on what you're doing in the threads. -- http://mail.python.org/mailman/listinfo/python-list
