While it is possible to use a Windows or NFS share for your Apple TimeMachine backups, using the native Apple file sharing protocol (AFP) together with a service like Bonjour to broadcast the file services available you will find yourself with a much better file sharing experience. This tutorial walks you through how to configure your Ubuntu server to serve as an AFP host on your network and then discusses what you will need for TimeMachine to work properly.
There are a number of affordable NAS solutions out there that can provide relatively inexpensive network addressable storage over NFS and SMB. Using a Mac with TimeMachine, an NFS server can be configured to provide storage for all of your backups. This article will walk you through setting this up, with the assumption that you already have the NFS storage device available on your network.