How does the OS know that a command needs sudo?

For the purposes you have described, the OS doesn't decide whether you need sudo to initially run the program. Instead, after the program starts running and then tries to do something that is not permitted by the current user (such as writing a file to /usr/bin to install a new command), the OS prevents the file access. The action to take on this condition is up to the program; make stops running but du will proceed to the next file/directory after printing a message.

The su and sudo commands are two different ways of running a program with root privileges. They may differ in minor details such as the contents of the environment when starting the new program, depending on options used. The OS does not need to decide when one or the other might work.

1. Sometimes the "Permission denied" message is due to filesystem permissions denying you write access, for example. The executable/tool simply checks if it the filesystem grants you enough permissions to do what you're about to do and throws an error if it's denied by the filesystem. Other times, the tool itself will check your user ID before allowing you to continue using it.
2. When you run a program with sudo you are running it under some other user's name. If that user is "able to do more things" than your user and the sudo configuration allows you to do these things on the other user's behalf then yes, sudo will allow you to do more things. This is not necessary, though. If you just tack sudo on at the beginning of the command line, you're actually sudoing as root, so typically you're able to do more things than a mere mortal.
3. Most definitely not. To use sudo you need to supply your own user password and then you're allowed to do some things on the target user's behalf. To use su, you need the target user's password and if you have it, you become that target user as far as the system is concerned and can do anything that user can do.

See also

• Why is the 'sudo' password different than the 'su root' password

su and sudo are privileged programs. su changes (after successful authentication) the real and effective user and group id to that of the user you su to. Thus, su is similar to login. Note that su can be used to change to any user, not just root. sudo also changes the real and effective user and group ids. Up to this point su and sudo are similar (but unrelated), beyond that they are very different.

With su, you need to know the target's password, and once you authenticated, you can do whatever you want as that user. The use of su can be restricted by setting SU_WHEEL_ONLY in /etc/login.defs. If it is set, only users in the group wheel may use su, otherwise it is not restricted. Apart from that, su is all or nothing.

sudo is completely different with respect to that. With sudo you can define quite complex policies in /etc/sudoers on what the sudoer (the user who calls sudo) is allowed to do. For instance, you can define policies where certain users may run only certain programs with certain privileges, while other users may run other programs with other privileges.

One of the striking features of sudo is that you can configure it such that a user has to authenticate himself with his own password (instead of that of the target). Thus, sudo has grown very popular amongst admins, for it allows to authorize users to do only defined privileged operations without dealing out the superuser password, plus you get some degree of accountability.