With the recent rebuild of my NAS finished I finally decided to tackle how to properly backup my MacOS machines.
All you need is a linux server and a recentish version of samba.
The configuration for the network share should look like the code snippet below. All you should need to change is the path.
Now you just need to restart samba.
In case your Mac does not automagically find the share you can manually set the timemachine destination with the following command
tmutil setdestination 'smb://user:password@server/timemachine'
Now you should have Timemachine working away on your mac!