PHP:
bool mkdir ( string $pathname [, int $mode [, bool $recursive [, resource $context ]]] )
This should help you. Create another box in your upload form that allows them to specifiy their directory.
I would suggest not allowing slashes or periods, and make sure those are filtered out, as it can lead to security issues very quickly.
Basically take $_POST['newdir'], where newdir is the name of the object in the form, and use mkdir to make the directory. After that you'll just have to decide how you want to prevent other users from accessing the wrong directories.
Oh, I'm assuming you know how to code PHP.. if you don't, you have very little chance of this succeeding without alot of help.