As the sibling comment suggests, multi-threading through Cython isn't as smooth as it could be. But, it doesn't seem too bad. I've used it in a rather rudimentary way to accelerate key computations for some NLP models that I've been playing with recently.
As an example in [1], you can check out the function at lines 293-314, which calls the function at 224-256 (or lines 259-291 depending on the machine architecture...). The actual dispatcher that initializes the threads is in [2]. I guess the key points are the use of "nogil" in the function declaration on lines 224-229, and the use of "with nogil" when that function is called on line 312. Note that the code is complicated a bit by my use of BLAS functions accessed via function pointers provided by SciPy.
The problem is that it's really nasty to declare all your functions nogil, because that means you don't get exception handling. There may be a trick to this that I've missed --- I find the GIL handling stuff in Cython sort of confusing.
I think my applications are genuinely hard to multi-thread, so maybe it's usually easier than I've found it. It doesn't help that I use a Macbook Air, and OpenMP isn't available for CLang. Developing on OSX sucks sometimes.
I'v had a lot of success with cython's parallelism. The key is to release the GIL in tight inner functions of big loops. You can then parallelize the loop by iterating over calls to the nogil function or "with nogil" block.
The support for only openmp kind of sucks, but I'm working on a Linux cluster so it doesn't bother me except when I'm on my laptop.
Sometimes it is possible to do long-running computations with pure C code and the GIL can be released. Mostly though you use Cython because it lets you combine Python code with C code, and any code that touches Python datastructures must hold the GIL. Therefore the same advice as for Python in general applies, use multiprocessing instead of threading.
I work with objective-c a lot and python was my first language, so to see this kind of unification just blows my mind.