Linking the new pages into the navigation will probably take care of itself once you find out why the AutoNav block is not included in the list of blocks you can add to a page.
Since this block is included in the core system, I wonder if there might have been a problem during the installation? (I'm presuming this is a new installation...) Is /concrete/blocks/autonav/ present in your file system? Is there a table in your database named "btNavigation"? Is there a record in the Blocktypes table in the database whose btHandle is "autonav"?