Codeigniter is designed to be an MVC framework which means:
model layer: read/writes to the database
view layer: the website's front-end skin
controller layer: retrieves data from the model layer and preps it for the view layer
You shouldn't really be including other php files in your views. However, if you're just trying to do a shared navigation menu, I guess that's alright. Put it wherever you want your navigation menu to be. All of the views should primarily just be templates.
MVC frameworks are very powerful tool, you just have to know their basic consruct.. otherwise you will be lost..
Once you've learned one of them, pretty much the rest are not too hard to understand, because they are almost all the same. Except, for the symfony it has some wicked derivatives that really need some close attention and learning.
By the time, you get into pagination with CI, you probably expert in routing all these files. Pagination in CI is pretty easy thing to do..