The "simple way":
Using the Keyboard Accelerator Keys
You can use the keyboard accelerator keys: Alt + F to bring up the file menu, and then W for the New menu, and then F for new folder. So your shortcut key sequence ends up being F + W + F with the Alt key held down. (Try it out)
Note: this combination depends on the language of your Windows system.
Alternative way 1:
Create your own shortcut like Ctrl + N with AutoHotKey
Script you have to hot key:
NOTE: "Display full path in title bar"
must be checked in "folder options" of
^N:: WinGetActiveTitle aTitle
InputBox, FolderName, Create New
Folder, What would you like to name
MsgBox "%FolderName%" has been created
in "%aTitle%". Return
Alternative way 2:
mdAxelerator v1.0 (~26k)
It enables defining the shortcut key for creating new folder and making possible to change some other "create new folder" behaviours like default new folder name. This version works only with 2k/xp/2k3 (no nt 4.0 and 9x - sorry).
There are some useful features added like auto enter into just created folder.