Create your new folder  in the under the 'Documents' folder hierarchy.
Right-click -> properties and at the bottom of the general tab you will see a
tickbox to 'Enable enhanced  Folders'. I dont think you can change a folder to
enhanced if there is anything in it ... it must be empty ... and the same goes
for changing it from enhanced to normal ... it must be empty.

I'm having trouble finding the Documents folder, I have shared documents
folder (http://sps2003/sites/123/shareddocuments) but not just a
Documents folder. Am I looking in the wrong place?

There are
no distinctions between Standard and Enhanced folders  in SPS 2003. These
Document Libraries are completely different beasts. Document Profiles in
2001 are now driven by custom columns unique to each Doc Lib, and there are
no workflow/routing features either (although you can enable basic approvals
for Doc Libs).