Redhat user:
chown 0:0 /bin/rpm && rpm -qa | xargs rpm --setugids
Debian/Ubuntu user:
chown 0:0 /bin/* /usr/bin/*
chown daemon:daemon /usr/bin/at
chown 0:utmp /usr/bin/screen
chmod 02755 /usr/bin/screen
chmod u+s /bin/fusermount /bin/mount /bin/su /bin/mount
chmod u+s /usr/bin/sudo /usr/bin/passwd
screen
While screen is running do this at least twice:
dpkg --get-selections | awk '{ if ($2 == "install") print $1}' \
| xargs apt-get install --reinstall --
Pay very close attention to the output because if it complains about something having the wrong permissions, you should fix it on another screen window.
Crash course in screen:
Control+A - command key
Control+A a - emit a control+A
Control+A n - next "screen"
Control+A c - create "screen"
Solaris user:
You're fucked.
pkgchk -R / -f -a
will reset all the permissions, but setuid-ness will still be broken. Use a backup, or another solaris machine to look for setuid/setgid scripts and files and fix them up manually.
THE IMPORTANT THING ABOUT BACKUPS
Is that you can recover them, not that you take them.
Other people have given you advice to take backups, but I want to add that you should be testing them. If you're using a unixish system, there is no reason whatsoever that you can't dump the files onto another machine periodically and make sure everything works.