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.
For anyone with an iPod Touch or iPhone, support on Linux has been somewhat limited until a few months ago. While it was possible to jailbreak your phone, this remains a sensitive and time consuming process. Fortunately, with the work on usbmuxd it is now possible to mount either one of these popular Apple devices on your favorite Linux distribution. There is still some configuration work necessary to piece everything together, but once it is running the support is relatively seamless.