How to upgrade Magento when the database structure changes between versions?

All of the upgrade methods I have seen (not sure about the magento connect method) do not touch the database only the files and & directories). I am on my first Magento build but I see that they have changed the directory structure with past updates. So my question is how should I update Magento to ensure the database gets upgraded?