First the tester should to go through the requirement, as to why the particular stored procedure is written for.
Then check whether all the required indexes, joins, updates, deletions are correct comparing with the tables mentions in the Stored Procedure. And also he has to ensure whether the Stored Procedure follows the standard format like comments, updated by, etc.
Then check the procedure calling name, calling parameters, and expected reponses for different sets of input parameters.
Then run the procedure yourself with database client programs like TOAD, or mysql, or Query Analyzer
Rerun the procedure with different parameters, and check results against expected values.
Finally, automate the tests with WinRunner.