To use NetInfo you just have to open up the program ( it is in /Applications/Utilities/ ). Open it up, then under one of the menu's it says enable root user, just do that and change the password. I find that using the CLI is easiar though. Just open up a terminal and type in 'sudo /bin/tcsh' then 'passwd root' and enter the root password. If neither of those ways work let me know, I'm in classic right now (my dad doesn't like X because it is slow) but anyways i can just boot into X and find the correct way to do it.
I noticed that if I login as a non-administrator and I attempt to "sudo", I get a cautionary message and then the password prompt. If I then enter the *correct* root password, I always get a "wrong password" error. If I login as adminstrator, I can sudo successfully, and I get the password prompt right away.
I assume non-administrators should also be able to sudo, otherwise why give the password prompt?
No, that is what is supposed to happen. If you edit the /etc/sudoers file, then you can control which users can use the sudo command and which users cannot use it. If everyone could use sudo, that would mean everyone would have full control over your computer.