Where to put third party PHP library?

If each plugin/theme functions on its own, then you should probably drop the the library in every theme/plugin.

Then just check to see if it a class or function from the third-party library exists before requiring it.

<?php
if( class_exists( 'SomeClass' ) )
{
    // require/include here
}

or

<?php
if( function_exists( 'some_function' ) )
{
   // Require/include stuff here
}

Alternatively, you could wrap every function/class/variable/constant from the third party library in a check to see if it exists, like pluggable functions.

If all of the plugins and the theme are dependent on one another, then it doesn’t really make much sense to divide them up and you should probably rethink that.