I'm not sure where the 'lib64' part is coming from. I would expect all files to
end up in $prefix/lib/site-packages/cairo. Is $prefix/lib64/site-packages a
standard python directory or is it specific to your Linux distribution?
If I do
$ cd Python-2.4.1/Lib/distutils
$ grep lib64 * */*
it returns nothing - lib64 does not look like a standard Python directory name
to me.

Are you building pycairo using configure/autogen or setup.py? (configure is the
preferred way to build pycairo, setup.py is a user contributed file)
Also what Python version and Linux distribution are you using?

I'm using FC4 for AMD64.
The /lib64 hierarchy is standard. From Filesystem Hierarchy Standard:

"The 64-bit architectures PPC64, s390x, sparc64 and AMD64 must place 64-bit
libraries in /lib64, and 32-bit (or 31-bit on s390) libraries in /lib."

As pycairo contains .so files, and those are compiled for my 64 bits
architecture, they should go under /lib64. Also, in FC4 at least, almost all
python modules are under /usr/lib64, although some go under /usr/lib.

I'm building pycairo using configure/autogen. Finally, it's version 2.4.1 of Python.

Here's a fix which should work:
edit cairo/Makefile.am
delete the line "pycairodir = $(pythondir)/cairo"
Change the line "nodist_pycairo_PYTHON = __init__.py" to
"nodist_pycairoexec_PYTHON = __init__.py"
rerun 'configure' and 'make install'.

Could you test it and report back to say if it was successful.

Success. That indeed corrects it for me.

Note: I just noticed that pycairo.pc is still under /lib/pkgconfig. There is no
problem with that. It all works. But maybe that should go under /lib64/pkgconfig.
Looking in /usr/lib64/pkgconfig on FC4 makes me believe that that is the correct
place for it.  (But, I'm now just bitching, for I lack a better thing to do; pay
me no attention. ;)

Thank you.

Patch applied to cvs, closing bug report.