¿? Pero si lo has puesto tu mismo...
Código PHP:
//Mostramos los registros
while ($row=mysql_fetch_array($result))
{
echo '<tr><td>'.$row["nombre"].'</td>';
echo '<td>'.$row["localidad"].'</td></tr>';
}
mysql_free_result($result)
?>
Eso va creando 2 celdas (columnas) por cada fila de una tabla y colocando las variables dentro, no tienes mas ke acomodar eso a tu diseño ya sea con tablas o css.