Install sudo from Synaptic. I don't see visudo in there, though. I don't know what package provides it.
[root@fatman ~]# which visudo
/usr/sbin/visudo
[root@fatman ~]# rpm -qf /usr/sbin/visudo
sudo-1.7.2-0.p4.4pclos2010.i586 <--- This one 
Thanks for clearing that up, O-P. I don't have sudo installed, and Synaptic doesn't list visudo as a dependency for the sudo package.
It's not a dependency... it's part of the sudo package.
[root@fatman ~]# rpm -ql sudo/etc/logrotate.d/sudo
/etc/pam.d/sudo
/etc/sudoers
/usr/bin/sudo
/usr/bin/sudoedit
/usr/bin/sudoers2ldif
/usr/sbin/
visudo <---- Here/usr/share/doc/sudo-1.7.2
/usr/share/doc/sudo-1.7.2/HISTORY
/usr/share/doc/sudo-1.7.2/PORTING
/usr/share/doc/sudo-1.7.2/README
/usr/share/doc/sudo-1.7.2/README.LDAP
/usr/share/doc/sudo-1.7.2/TROUBLESHOOTING
/usr/share/doc/sudo-1.7.2/UPGRADE
/usr/share/doc/sudo-1.7.2/WHATSNEW
/usr/share/doc/sudo-1.7.2/sample.sudoers
/usr/share/man/man5/sudoers.5.bz2
/usr/share/man/man8/sudo.8.bz2
/usr/share/man/man8/sudoedit.8.bz2
/usr/share/man/man8/visudo.8.bz2
/var/log/sudo.log
/var/run/sudo