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

$this->paginate = array(
	"contain"=>array(
		"id", "first_name", "last_name",
		"Title"=>array(
			"name"
		)
	)
);
 
$this->set("data", $this->paginate("User"));

Happy Baking! :-)