1) Save backup

if you have enough free space on the server you can backup your server locally to /home/backup:
mkdir -p /home/backup

tar -cvpzf /home/backup/backup.tar.gz \
--exclude="/home/backup/*.tar.gz" \
--exclude="/lost+found" \
--exclude="/dev/*" \
--exclude="/proc/*" \
--exclude="/sys/*" \
--exclude="/media/*" \
--exclude="/mnt/*" \
--exclude="/tmp/*" \
--exclude="/var/cache/apt/archives/*.deb" /


If you have other directories that you want to exclude from the backup, you can add more excludes.

If you don't have enough free space on the server, you can save the backup to the remote server via ssh:
tar -cvpzf - \
--exclude="/lost+found" \
--exclude="/dev/*" \
--exclude="/proc/*" \
--exclude="/sys/*" \
--exclude="/media/*" \
--exclude="/mnt/*" \
--exclude="/tmp/*" \
--exclude="/var/cache/apt/archives/*.deb" / | ssh -t user@remotehost "cat > backup.tar.gz"


2) Restore backup

Run any livecd, for example systemrescuecd and create swap root and home partitions via fdisk or parted. I recommend to create at least swap root home and var but you may want to create swap and root only - whatever...
We assume that the swap is /dev/sda1 and the root is /dev/sda2 - let's make fs on partitions:
mkswap -L SWAP /dev/sda1
mkfs.ext4 -L ROOT /dev/sda2

Mount it to /tmp/target:
mkdir /tmp/target
mount -t ext4 /dev/sda2 /tmp/target

Mount dev, proc, sys:
mount --bind /dev /tmp/target/dev
mount --bind /proc /tmp/target/proc
mount --bind /sys /tmp/target/sys

Chroot to /tmp/target:
chroot /tmp/target

Modify /etc/fstab to suit your partitions. It can be LABEL or UUID or /dev/* - run blkid and check it out.

Install bootloader:
grub-install /dev/sda

Update initramfs:
update-initramfs -uk all

Update bootloader:
update-grub

Exit chroot and reboot:
exit (or Ctrl+D)
reboot
If there are no errors, the new server will boot :)
This method is suitable for most distributions, Debian, Ubuntu, etc. For RedHat based or if you use LVM this method requires specific changes.
There are other ways, for example dd, but that's another story.