Be sure to setup the ORM object prior to initializing Paginate and you should have no issues using relationships. Keep in mind that Paginate is simply building atop your object prior to pulling a response.
If the relationship is being handled in the ORM class, there is nothing special to do with Paginate. Recommend prefixing the column names with the table name ("post.id" for example). If you are joining outside of ORM, be sure to do so prior to passing ORM to Paginate:
$post = ORM::factory('post')
->join('category')
->on('post.id', '=', 'category.post_id');
$paginate = Paginate::factory($post)
->columns(array('post.id','category.name'))
->execute();
I'm the creator and maintainer of Paginate and am happy to answer any questions you might have. Thank you.