This was not that hard! First look at what everyone else has to say about this, nice aggregated on the python wiki. It covers a lot.
Now for what I discovered on top of this:
When you're defining a new type self->ob_type doesn't exist anymore. This is a problem as you need it in the deallocator for example. The solution is to use Py_TYPE(self). So the deallocator becomes: Py_TYPE(self)->tp_free((PyObject*)self);
When you're paranoid and use -Werror -Wredundant-decls you'll notice a duplicate declaration in pyerror.h. Bug filed.
The module initialisation is a lot easier then in the official docs. You seem perfectly fine without module state, so all you need to fill out in your struct PyModuleDef is m_base, m_name and m_size. Of course m_doc and m_methods are pretty useful too, but not strictly required. Copy the tutorial here.
And if you use PyMODINIT_FUNC to declare it all you need to #ifdef is PyInitmymodule(void), PyModule_Create() and the return value.