At a minimum, you document it like you would a function or method in source code. For example:

• What does the stored procedure do? Does it update or modify any tables or just read values?
• What are the arguments? What are their allowed values? Can they be NULL?
• What is returned? Is it a scalar value? Is it a table? If so, what are the fields and what do their values mean? Is there a single row or multiple rows?
• Give an example of its use
• Are there related or similar stored procedures? For example, is it normally used in conjunction with another stored procedure?

Depending on your environment, the following may or may not apply:

• Should it be called within a transaction or not?
• Are there any special security requirements? For example, does the caller need access to particular tables?
• Are there any known bugs that are not fixed due to backwards compatibility reasons?
• Does this stored procedure supersede other stored procedures? Is it obsolete or deprecated?
• Is the stored procedure written by hand or auto generated? If it is auto generated, what tool generated it?
• Does the procedure deal with sensitive information like credit card details, hashed passwords or Personally Identifiable Information (PII)?

For the actual documentation, the best experience I had was using a Wiki. Each stored proc had its own page and so the documentation was versioned independently with an easily accessible history and change list. Users could subscribe to changes via E-mail and the documentation was always in an easily accessible location.