En el primer caso sería:
Lanzas una consulta que cuente la cantidad de registros existentes en la tabla "SELECT COUNT ...". Luego, podrías hacer un if preguntando si la cantidad de registros es menor que 60, en casi positivo, haces la nueva inserción, en caso negativo, no haces la inserción y le decís al usuario de alguna manera que no puede insertar más registros.
La idea del procedimiento almacenada es exactamente la misma, pero en ves de que el código de esa validación esté en tu aplicación, estará en un procedimiento guardado en la base de datos, y para insertar un registro, llamás a ese procedimiento el cual determina o no si se puede hacer la inserción.
Si quieres ver un poco de programación de procedimientos almacenados, acá tenés una guía:
http://dev.mysql.com/doc/refman/5.0/...rocedures.html