Partition your disk locally first. You can't partition it while its on the network (easily). Use Disk Utility, click the name of your drive (not a partition) and go to the Partition tab. Click the + and adjust the size as you wish. Then, name it and change the format to MS-DOS (FAT). Click Apply to apply your changes.
Then, adding onto Alain's answer, here is a detailed explanation and instructions in Terminal on how to setup a network-attached storage device with Time Machine.
It's more complicated than it might seem, but here's a rundown of the steps provided by the above link:
Make sure that the network device is mounted. Then, open Finder and at the menu bar, click Go > Network. Double-click your storage device and enter any authentication details if needed.
You'll need to find the name of your computer on the network. Go to System Preferences > Sharing and make a note of what it says as "Computer Name."
Enter Terminal. You can find it in /Applications/Utilities.
Run defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1 to allow Time Machine to work with devices that it normally doesn't.
Next, we'll need to find the MAC address of your computer. Run ifconfig en0 | grep ether
The output should look like ether XX:XX:XX:XX:XX:XX - make a note of everything after ether.
Next, we'll have to create a .sparsebundle for Time Machine. Read this carefully, as this is a pivotal step in the setup process.
Still in Terminal, run hdiutil create -size 100g -fs HFS+J -volname "Time Machine" NAME_XXXXXXXXXXXX.sparsebundle - where NAME is the name of your computer (all spaces will be dashes) and the X's are your MAC address without colons.
Also, make sure that the -size argument is the space you want to create for your Time Machine. This will make the partition in HFS+J however large you want. In this particular command example, we have created a 100 GB partition for Time Machine.
You can replace -size 100g with anything you want ( 50g, 150g, even OVER 9000g [but only if your NAS has this much capacity])
Next, run rsync -aE NAME_XXXXXXXXXXXX.sparsebundle /Volumes/DRIVE/. - where DRIVE is the name of your storage drive. Remember that NAME is your computer name with dashes and the X's are your MAC address without colons.
You can also simply type rsync -aE NAME_XXXXXXXXXXXX.sparsebundle and drag in your network drive icon from Finder; it'll automatically enter its name after. This step might take a few moments. Wait for it to finish; you'll know when it prints Your-Mac-Name:~ Username$ again.
Final Terminal command: rm -rf NAME_XXXXXXXXXXXX.sparsebundle to remove the copy of the .sparsebundle from your computer. After this, you can close Terminal (whew).
You can start backing up as normal now. Go to System Preferences > Time Machine and click Choose Backup Disk... and select your network drive.
Although it will show the drive's full capacity, Time Machine will be limited to the size specified in the step where you ran hdiutil create by the -size argument.
Time Machine will start backing up.