The Documents module is very simple (maybe too much so).  To be able to upload you must have "EDIT" rights to the module.  If you extend "EDIT" rights for the module to your users' then they'll see the "Upload" link but....they will then also be able to delete and/or modify existing documents or even delete the documents module itself.  You probably don't want that.
 
Instead of "Documents", you probably want "Repository" which is more complex but more full-featured.  "Repository" will allow "moderated uploads" where you can allow anyone to upload without having "EDIT" rights to the module.  You can require uploaded documents to the "approved" by a moderator before they will appear on the list of availabel docs.  "Repository" also features results paging (in case you have LOTS of files) as well as a file search function.  The module is even skinnable which is handy if you really need the look of the module content to match your site.  "Repository" will take a little head scratching to figure out the first time you use it but it's a great module once you've got it figured out.
 
Cheers!
-mamlin