Gracias Cluster, lo que mencionas del session_start esta en el código siguiente.
  Código PHP:
    if($array = mysql_fetch_array($query)){
    session_start();
    $_SESSION['autentificado'] = "SI";
    $_SESSION['usuario'] = $array["Username"];
} else {
    header("Location: index.php?errorusuario=si");
} 
    
  Pero no se si lo que me indicas es que lo tenga que usar antes o fiera del condicional para así manejar una sesion sea un usuario logeado o no. 
Lo del SID lo he leido y no lo entendi mucho pues tengo entendido que es global, siempre y cuando sea inciada la sesión, ahora, como tendria que ser el código para hacer las cookies, seria con setcookie, de ser así que me recomiendan, 
La forma manual es agregar a todos los enlaces del sitio la variable del SID no? Acaso existe otra forma, pues eso seria bastante engorroso y muy largo, existe una forma automática, como la uso? 
Referente a la configuración de mi servidor, y partamos de la hipotesis de que el navegador del cliente acepta las cookies. 
session.use_cookies     On
session.use_trans_sid    1 
Gracias nuevamente,