Help me backup my computers

I'm thinking of setting up some kind of backup server to backup all of my computers, but I'm not really sure where to begin. I have a mix of windows and linux computers which I'd like to be able to backup automaticly to a central server, Ideally something which will run on my current ubuntu server but I don't really mind setting up a VM for something else.

If anyone has any experience with this it would be really great to hear your opinions and ideas.

I've been looking at backuppc and I think I will have a play with it but I don't really have any experience with backing up and restoring computers so I don't know what to look for.

I'd like something which will run in the background without slowing down my computers too much. I'd also like something which has a sort of history so I can roll back to a previous backup, kind of like shadow copy.

Also it would be great to hear some tips to make restoring a backup more painless.