Хм, добре, след като се зарових в документацията на postgreSQL, намерих решение в Функции и оператори за низове раздел.
Използвах convert(string bytea, src_encoding name, dest_encoding name)
функция и успя да получи идентификатора на провинция за Квебек.
Пр.
String query = "SELECT id FROM province WHERE name = convert( 'Québec', 'UTF-8', 'ISO-8859-1' );";