Procedimientos Almacenados

Primero que nada comentar que MySQL solo soporta procedimientos almacenados a partir de la versión 5.0.x así que si tienes una inferior debes upgradear antes.
Hechale un vistazo a esto: http://dev.mysql.com/doc/refman/5.1/en/stored-procedures.html Esta en ingles pero debe ayudarte a comprender como trabajar con ellos en MySQL.

Lo del PHP más o menos lo tengo claro pero, por ejemplo, cómo sería un proc. alm. ¿qué me devolviera un conjunto de datos? ¿Qué tipo de parámetros se utilizaría? Típico listado ordenado que se devuelve realizando un cursor o algo similar.
Muchísimas gracias por tu tiempo.
Un saludo