Linux - What directories should I exclude when backing up a server?

This really depends on how you are going to restore your system. If you will rebuild then you only need the configuration/data files for your services (eg: /etc, /opt, /var, /home)

If you are after a full system restore, then it you could omit /proc, /boot & /dev. Then you can install the minimum OS from your boot media and then restore your system via your backup.

Of course, the best backup is one that has been tested and verified.

So omit what you don't think you need, try to restore in a VM and verify you can get back your system using this data.

Both /proc and /sys are virtual filesystems which reflect the state of the system, and allow you to change several runtime parameters (and sometimes do more dangerous things, like directly writing to the memory or to a device). You should never backup or restore them.

In most modern distributions, /dev is dynamically created at boot (it is a memory filesystem filled by udev and friends). There is no point in backing it up, and attempting to restore it is futile. However, if your distribution is configured to use a static /dev, this does not apply (check /proc/mounts, if /dev is a tmpfs it is a memory filesystem).

There are other filesystems you should not back up; usbfs (usually at /proc/bus/usb, if mounted at all), debugfs (supposed to be at /sys/kernel/debug if mounted at all, but some people put it somewhere else; you probably do not have this one), devpts (mounted at /dev/pts), other tmpfs instances (often found at /dev/shm, /var/run, /var/lock, and other places; backing them up and restoring them should be harmless but pointless, as their contents are lost on shutdown), and any remote filesystems or magic automounter directories (attempting to backup or restore them could end up in disaster, as you could end up backing up/restoring to a different machine). You should also be careful with /media and /mnt, as external devices (like a CD you forgot in the drive) could be found there, but you might also have used them on purpose to mount something which should be backed up.

Note that, other than mostly harmless tmpfs instances, network filesystems/automounters, and removable media, the filesystems you should not back up are all descendents of /dev, /proc, or /sys. If you have no network filesystems (or automounters), and no removable media, excluding /sys and /proc and rebooting after a restore (to wipe the tmpfs instances) should be enough.

See The Tao Of Backup, chapter 1.