I think I have found the answer now (thanks to the pointers from Tshepang):
In debian/rules you need to invoke dh_pysupport.
This grabs all the files installed by setup.py on the build machine in
$(DESTDIR)/usr/lib/pythonX.Y/dist-packages/mymodule*
and puts them into a non python-version specific location in the .deb file, namely
/usr/share/pyshared/mymodule*
finally, it adds a call to update-python-modules to the postinst script, which makes sure that the module is available on every version of python present on the target machine.