I don't think I would want users creating directories on my server and then loading files, but it can be done.
Depending on the platform you are running on, mkdir can create directories with proper permissions. If you are on A *nix box with Apache and PHP as an Apache mod, then your scripts run as the apache user (usually, nobody or apache). In order for your scripts to be able to create a drectory, apache's user would have to have X and R permissions on the dir you want to create the sub dirs in.
If PHP runs as a CGI wrapper, then the user your scripts run as need to have the proper perms.
Don't forget to check if a dir exists before you create it.