Aquí te muestro una forma de ordenar por nombre de provincias. Los pasos a realizar son los siguientes:

• Extraer las provincias solamente (nombres).
• Extraer las poblaciones solamente (sets).
• Ordenar el nombre de las provincias. Para ello hacemos uso de Collections.sort(List<T> list), que ordena una lista en forma ascendente.
• Recorremos las provincias ordenadas e internamente recorremos la lista de poblaciones.
• Comparamos el nombre de la provincia actual por cada nombre de provincia del objeto Población de cada Set (en mi caso getStateName()).

Por ejemplo, la problación Leganes tiene la siguiente estructura:

Nombre de provincia: Leganes
Número de ? (no sé que significa ese número): 345
Nombre de estado: Madrid (éste viene a ser la provincia madre) -> getStateName().

• En caso haya coincidencia agrega ese Set a una nueva lista de Set que estará ordenada gracias a la lista de provincias ordenadas.
• Por ultimo, cuando ya tenemos las listas de provincias y la lista de Set poblaciones ya ordenadas, las agregamos a un nuevo Map y lo retornamos.

NOTA: Se hace uso de la implementación de Map LinkedHashMap ya que HashMap no respeta el orden de inserción. Por el contrario, LinkedHashMap sí respeta.

Solo colocaré los nuevos métodos.

public Map<String, Set<Population>> sortBy(int sortType) {
		Map<String, Set<Population>> sortedProvincesAndPopulations = null;
		if(sortType == SORT_BY_NAME) {
			List<String> sortedProvinces = new ArrayList<>();
			List<Set<Population>> populations = new ArrayList<>();
			List<Set<Population>> sortedPopulations = new ArrayList<>();
			sortedProvincesAndPopulations = new LinkedHashMap<>();
 
			populations = getPopulations();
			sortedProvinces = getProvinces(populations);
 
			Collections.sort(sortedProvinces);
 
			/* Compara el nombre de la provincia de la lista ya ordenada con la
			 * lista de poblaciones. Si coinciden se agrega este Set poblacion a la lista
			 * de poblaciones ordenada.
			 * getStateName() : devuelve el nombre de la provincia que alberga esa poblacion */
			for(String provinceName : sortedProvinces) {
				for (Set<Population> population : populations) {
					sortPopulations(population, provinceName, sortedPopulations);
				}
			}
 
			fillNewSortedProvincesAndPopulations(sortedProvincesAndPopulations, sortedProvinces, sortedPopulations);
 
		} else {
			// el otro tipo de ordenamiento
		}
		return sortedProvincesAndPopulations;
	}

Métodos de ayuda:

private List<Set<Population>> getPopulations() {
		List<Set<Population>> populations = new ArrayList<>();
		for(Map.Entry<String, Set<Population>> entry : provincesAndPopulations.entrySet()) {
			populations.add(entry.getValue());
		}
		return populations;
	}
 
	private List<String> getProvinces(List<Set<Population>> populations) {
		List<String> provinces = new ArrayList<>();
		for(Set<Population> population : populations) {
			provinces.add(getKeyOfValue(population));
		}
		return provinces;
	}
 
	private String getKeyOfValue(Set<Population> population) {
		String key = null;
		for(Map.Entry<String, Set<Population>> entry : provincesAndPopulations.entrySet()) {
			if(population.equals(entry.getValue()))
				key = entry.getKey();
		}
		return key;
	}
 
	private void sortPopulations(Set<Population> population, String provinceName, List<Set<Population>> sortedPopulations) {
		for (Population objPopulation : population) {
			if (objPopulation.getStateName().equals(provinceName)) {
				sortedPopulations.add(population);
				break;
			}
		}
	}
 
	private void fillNewSortedProvincesAndPopulations(Map<String, Set<Population>> map,
			List<String> provinces, List<Set<Population>> populations) {
		for(byte i=0; i<provinces.size(); i++) {
			map.put(provinces.get(i), populations.get(i));
		}
	}

El método getKeyOfValue recibe un valor del Map y devuelve la llave (nombre de la provincia) asociada a dicho valor (Set<Population>). Aquí hacemos uso de equals() para comparar objetos.

Como comentario interesante, el método sort() de la clase Collections hace uso internamente de compareTo(). A éste método también le puedes pasar un objeto que implemente la interface Comparator<T> y que sobreescriba el método compare(), para que sort() ordene los elementos de la colección de acuerdo al método compare sobreescrito.

---

Prueba:

public static void main(String[] args) {
		PopulationService populationService = new PopulationService();
 
		Population population = new PopulationImp("Leganes", 345, "Madrid");
		populationService.addProvinceAndPopulation("Madrid", population);
 
		population = new PopulationImp("Ciutat Vella", 0, "Barcelona");
		populationService.addProvinceAndPopulation("Barcelona", population);
 
		population = new PopulationImp("El ensanche", 0, "Barcelona");
		populationService.addPopulation("Barcelona", population);
 
		population = new PopulationImp("La Zaidía", 345, "Valencia");
		populationService.addProvinceAndPopulation("Valencia", population);
 
		population = new PopulationImp("Castilleja de campo", 120, "Sevilla");
		populationService.addProvinceAndPopulation("Sevilla", population);
 
		System.out.println("\n*** Mostrando todas las provincias y sus poblaciones ***\n");
		populationService.showAll();
 
		System.out.println("\n*** Mostrando lista después de ordenar... ***\n");
		Map<String, Set<Population>> sortedPopulations = populationService.sortBy(0);
		for(Map.Entry<String, Set<Population>> entry : sortedPopulations.entrySet()) {
			System.out.println("Provincia: "+entry.getKey()+"\n");
			for(Population pop : entry.getValue())
				System.out.println(pop);
		}
 
	}

Resultado de ejecución:




El otro tipo de ordenar te lo dejo a ti. Por cierto, marca el otro tema como Solucionado para evitar confusiones.

Salu2.