Just to add to titanium_geek post lib z would not be removed when you remove prog x.
I downloaded ubuntu the other day and was very impressed, painless install and I loved the way it didn't set a password for root and encourages the use of sudo.
Package managers are different from one distro to another but when you have grasped the concept and have a deeper understanding of the system it will not be difficult to learn how to use other package managers.
The package managers do keep track of whats installed the only advantage this offers is that some authors do not write an uninstall script into their Makefile so when compiling and installing from sources you can not uninstall without manually tracking down and deleting all the files.
If you want to get 'under the hood' then forget the package managers, that just adds another level of complexity to worry about. Try slackware, slackware is one of the simplest distros going in that what you see is what you get, all the configuration is done with a text editor, the package manager is very simple and you can use checkinstall to keep track of programs you install from source