Which are the most important directories to backup on a Linux server?

The important directories are /etc, /home, /var, and /srv. You may want to add /root, and remove unneeded bits from /var.

rsync is good if you want the files to be directly accessible, tar is fine if you don't.

I agree with Ignacio Vazquez-Abrams about /etc/ /home/ and some parts in /var/.

But don't forget to save a list of the installed packages, so you know what programs was installed...

dpkg --get-selections > dpkg.list

I'm using backup2l to backup my Debian server (AFAIK Ubuntu is a derivative of Debian). If configured correctly it automates your backup, e.g. getting the dpkg selections, creating differential and incremental backups (depending on your settings) and storing it in an archive. A post backup hook triggers rsync which syncs my archive with a remote copy.

I'm backing up /etc /var (with some exclusions like caches), /root, /home. Just think about what you have changed in addition to that and add it to the list. I for instance dump my sql databases in a special directory and save it, too.