Add locale, e.g. pl_PL.UTF-8, you don't have to set it as system default:
dpkg-reconfigure locales
Install PostgreSQL
apt-get update
apt-get install posgresql-9.4
Installation adds a cluster with default locale, recreate it with the correct one. The operation will destroy existing data in the cluster.
pg_dropcluster --stop 9.4 main
pg_createcluster --locale pl_PL.UTF-8 --start 9.4 main
The resulting output may report incorrect locale, it will be system locale. However cluster will be set up correctly, to verify it run following queries:
su - postgres -c psql
show LC_COLLATE;
show LC_CTYPE;
\q
Now you can load locale sensitive data.