The root password can only be changed by the root user. Anyone who knows the root password can become root. The record of who did this requires several layers of inspection. First, you need to narrow the possible timeframe for the change. When was it happened? 1 hour ago, 4 hour ago or 2 days ago.
# /usr/lbin/getprpw -m spwchg root spwchg=Sun Jan 30 12:12:21 2011
This will show the date and time it was changed. However, unless you can track who was logged in as root at that time, or possibly who has sudo root access, then it will be quite difficult to determine who changed it.
Then, you look at the output from the last command to see all root logins:
# last -R -100 root
This shows the last 100 successful root logins including date and time and the first 15 characters of the hostname performing the login. Look at the time logins during the suspect time range. If rlogin is allowed and configured for root, there is not much you can do except to assume your machine has been hacked. rlogin, rexec and remsh (rsh from other boxes) are terrible security risks and should be disabled on all machines.
Once you regain control of your machine, you change the root password and do NOT tell anyone else what it is. You then install sudo and add only very few users to the sudoers file. And do not give those users every command, especially not a shell or the (ALL) capability.