Though, Tony already posted the magic command to make non-local volumes (connected through smb, nfs or afp) visible to Time Machine, I want to give a brief description on how I configured Time Machine on my MacBook Pro to use a Windows share.
1. First let’s make sure the volume isn’t already mounted:

2. Now mount the Windows share in Finder (Command (Apple) – K):


3. The Windows share will appear in the ‘Shared” section in Finder:

4. To verify, open Terminal and check the mounts:

5. Enter “defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1″ in the Terminal window to make unsupported network volumes visible to Time Machine:

6. Now you can configure Time Machine (System Preferences -> System -> Time Machine):



7. Done. Time Machine is now ready to backup your data…

8. …unfortunately there is not enough space on the Windows share

9. But at least you can see that Time Machine tried its best:

BTW, with “defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 0” you can revert the setting.