Podría ser:
Código PHP:
$query = "select * from usuarios WHERE nick LIKE '".$_GET['letra']."%'";
(con comillas simples '' ... )
Así formas tus links tipo:
nose.php?letra=a
Hasta puedes hacer un for() para generar esos links en función del abecedario (hay una FAQ de las últimas que trata ese tema).
Un saludo,