I just updated to iOS5 recently on my work 3GS phone until my new iPhone 4S arrives and just learned how to do this yesterday. If you have iOS 5 do the following:
Click on your Mail icon
Go to your mailboxes screen. At the top it will have all the mailboxes listed that you have set up at the top. Mine lists All Inboxes, Hotmail and my work email box. Below that it will say "Accounts" and will list the accounts for these email addresses.
Select Hotmail and it will bring you to another screen that shows the folders you already have in place.
If you click on Edit in the upper right hand corner, this is where you can add the folders.
Look down at the bottom and it will say "New Mailbox"
Click on that and type in the name of the new folder and click save in the upper right hand corner once that is done.
The new folder will now be added to the others you already had there and will be listed alphabetically.
To move an email to one of these folders, open it up and on the bottom you should see a folder icon with a down arrow on it.
Click on that and select the folder you want that email moved to and it will be dropped into that folder.
