Sudo is a program that:
1. Parses the sudoers file to check if the current user can run the command provided.
2. If so, authenticates the user using PAM.
3. If both those pass, sets the user id to root and runs the program.
There is nothing special about it. All steps can be done by any program. In fact sudo is usually not even an installed by default package in many systems.
The only seeming magic bit is part 3, where the program sets it's user id to root. Obviously if any program could do this... That'd be unsafe.
However, unix systems allow any executable file to have their flags changed to include the setuid bit which causes the file to execute with privileges of the files owner. You'll notice that the sudo binary has this bit set and it's owned by root, which explains now the entire process.