... de acuerdo, solo algunos detalles:
 
- 

 no es necesario crear "una variable de sesión", pero sí inicializarla (juego de palabras?)... no puedes destruir algo que no existe. 
- ... no es tanto que no se pueda usar 
session_start() antes de 
header(); sí se puede... pero ninguna de estas dos funciones las puedes usar si ya antes haz enviado a imprimir algo (lease la documentación oficial).  
- 
mysql_num_rows() devuelve los resultados de una consulta, antes tienes que hacer dicha consulta como dice 
chiriro... pero para poder hacer la consulta antes haz de conectarte. Sugeriría visitar las FAQ ó ver algún script de una consulta cualquiera. Las funciones que debes ocupar (en ese órden) son:
- mysql_connect()
- mysql_select_db()
- mysql_query() 
... y agregar que después de un header() debe llevar un 
exit; manejas eso solo en el primero. 
Un saludo.