Took me a little while to work this out so I'm blogging it here in the hopes it will help someone in the future:

Need to Contain your Paginated data?

in your controller:

$this->paginate = array(
	"contain"=>array(
		// usual contain array
	)
);
 
$this->set("data", $this->paginate("Model"));

For example, to bring back and paginate a User (id, first_name, last_name) and their Title (Mr, Mrs, etc.):

/app/users_controller.php