Si entendí bien, $_SESSION['s_concellos_ourense'] es un arreglo cuyos elementos también son arreglos. La forma de acceder a los elementos seria:
$_SESSION['s_concellos_ourense'][$indice]['Concello']
Además, podrías utilizar foreach, para simplificar el recorrido del arreglo:
Código PHP:
<select name="localidades" size="15" multiple>
<? foreach($_SESSION['s_concellos_ourense'] as $valor){ ?>
<option value="<? echo $valor['Concello']; ?>">
<? echo $valor['Concello']; ?></option>
<? } ?>
</select>
Saludos.