Follow the directions here, under "Setting up your project file."

Setting up your project file

You need to add libxml2.dylib to your project (don't put it in the Frameworks section). On the Mac, you'll find it at /usr/lib/libxml2.dylib and for the iPhone, you'll want the /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS4.0.sdk/usr/lib/libxml2.dylib version.

Since libxml2 is a .dylib (not a nice friendly .framework) we still have one more thing to do. Go to the Project build settings (Project->Edit Project Settings->Build) and find the "Search Paths". In "Header Search Paths" add the following path:

$(SDKROOT)/usr/include/libxml2

Also see the OP's answer.