This is really two questions, but they are so similar, and to keep it simple, I figured I'd just roll them together:

Firstly: Given an established python project, what are some decent ways to speed it up beyond just plain in-code optimization?
Secondly:  When writing a program from scratch in python, what are some good ways to greatly improve performance?

For the first question, imagine you are handed a decently written project and you need to improve performance, but you can't seem to get much of a gain through refactoring/optimization.  What would you do to speed it up in this case short of rewriting it in something like C?
People have given some good advice, but you have to be aware that when high performance is needed, the python model is: punt to c.  Efforts like psyco may in the future help a bit, but python just isn't a fast language, and it isn't designed to be.  Very few languages have the ability to do the dynamic stuff really well and still generate very fast code; at least for the forseeable future (and some of the design works against fast compilation) that will be the case.
So, if you really find yourself in this bind, your best bet will be to isolate the parts of your system that are unacceptable slow in (good) python, and design around the idea that you'll rewrite those bits in C.  Sorry.  Good design can help make this less painful.  Prototype it in python first though, then you've easily got a sanity check on your c, as well.
This works well enough for things like numpy, after all.  I can't emphasize enough how much good design will help you though.  If you just iteratively poke at your python bits and replace the slowest ones with C, you may end up with a big mess.  Think about exactly where the C bits are needed, and how they can be minimized and encapsulated sensibly.
Speeding Up Python