I'm going to break up my answer into three parts. Profiling, speeding up the python code via c, and speeding up python via python. It is my view that Python has some of the best tools for looking at what your code's performance is then drilling down to the actual bottle necks. Speeding up code without profiling is about like trying to kill a deer with an uzi.
If you are really only interested in mat-vec products, I would recommend scipy.sparse.
Python tools for profiling
profile and cProfile modules: These modules will give you your standard run time analysis and function call stack. It is pretty nice to save their statistics and using the pstats module you can look at the data in a number of ways.
kernprof: this tool puts together many routines for doing things like line by line code timing
memory_profiler: this tool produces line by line memory foot print of your code.
IPython timers: The timeit function is quite nice for seeing the differences in functions in a quick interactive way.
Speeding up Python
Cython: cython is the quickest way to take a few functions in python and get faster code. You can decorate the function with the cython variant of python and it generates c code. This is very maintable and can also link to other hand written code in c/c++/fortran quite easily. It is by far the preferred tool today.
ctypes: ctypes will allow you to write your functions in c and then wrap them quickly with its simple decoration of the code. It handles all the pain of casting from PyObjects and managing the gil to call the c function.
Other approaches exist for writing your code in C but they are all somewhat more for taking a C/C++ library and wrapping it in Python.
Python-only approaches
If you want to stay inside Python mostly, my advice is to figure out what data you are using and picking correct data types for implementing your algorithms. It has been my experience that you will usually get much farther by optimizing your data structures then any low level c hack. For example:
numpy: a contingous array very fast for strided operations of arrays
numexpr: a numpy array expression optimizer. It allows for multithreading numpy array expressions and also gets rid of the numerous temporaries numpy makes because of restrictions of the Python interpreter.
blist: a b-tree implementation of a list, very fast for inserting, indexing, and moving the internal nodes of a list
pandas: data frames (or tables) very fast analytics on the arrays.
pytables: fast structured hierarchical tables (like hdf5), especially good for out of core calculations and queries to large data.
