UPD: Весной 2015 года отменили выдачу PESEL для иностранцев. Теперь в документах, которые подразумевают указание PESEL иностранец указывает просто свою дату рождения. Если песел необходим и без него никак, то его можно получить приложив к заявлению письменное обоснование в связи с чем он понадобился.
Запись ниже уже устарела :(

PESEL — это некий идентификационный номер, к которому привязаны практически все документы и финансовые операции. Для его получения нужно иметь регистрацию по месту жительства в Польше и действующую рабочую визу. Во Вроцлаве регистрация и выдача PESEL происходит в отделениях обслуживания жителей. Адреса на сайте Вроцлава – www.wroclaw.pl/centrum-obslugi-mieszkanca. Я регистрировался на ул. Г. Запольской около Аркады. Вся процедура занимает минут 10 и несколько минут в очереди. Происходит так: в рабочее время с 8ми до 4х приходим по адресу, находим стойку информации говорим, что нужен мельдунек (регистрация). Если Вы в нужном зале, то Вам покажут терминал, который печатает талоны электронной очереди или даже помогут выбрать пункт меню и распечатать талон. Если вы не в том зале, вам покажут где искать правильный.

С собой нужно иметь заполненный бланк Е-3 (можно на месте взять и заполнить). Временная регистрация производится на срок до трех месяцев. Это нужно учитывать при заполнении дат в бланке. Также нужен договор аренды жилья (оригинал), в котором указан срок аренды, Ваши данные, данные хозяина и адрес помещения. Ну и загранпаспорт с визой на весь срок регистрации. Сотрудник проверяет документы, может что-то уточнить и/или исправить прямо на заявлении (переписывать заявление в случае ошибок не нужно). Если с документами все в порядке, то Вам на месте выдают бумажку с печатью и подписью, в которой сказано что Вы уже зарегистрированы. PESEL они отправляют по почте на адрес прописки обычным письмом. В течение недели он будет у Вас.

Если едете с супругом, то ему/ей тоже нужно будет зарегистрироваться. Для этого в договоре аренды должно быть указано, что супруг тоже будет проживать в той же квартире. PESEL выдают только тем, у кого рабочая виза.

После получения PESEL и регистрации можно продолжать легализацию долгосрочного пребывания. Алгоритм такой: получаем или покупаем мед. страховку, получаем выписку из налоговой, подписываем на работе контракт на неопределенный срок, делаем фото и подаем документы на карту побыту (временный вид на жительство, residence permit). Она дается на срок до 3-х лет и дает право пересекать границы самой Польши, ездить в сраны евросоюза на срок до 3-х месяцев в году. После трех лет пребывания можно подавать документы на постоянный вид на жительство. Еще через два года можно подавать документы на гражданство. Но есть обходной маневр. Прошение о предоставлении гражданства можно подавать в любой момент на имя Президента РП. Эта процедура ничем не регламентируется и решение не обжалуется. НО! Во-первых не нужно ждать пять лет, во-вторых, она бесплатна, в-третьих количество попыток не ограничено.

UPD. Кроме PESEL есть еще NIP. PESEL — это просто уникальный идентификатор человека в государстве. NIP — это номер связаный с налоговой отчетностью. Можно иметь PESEL, но не иметь NIP. Можно наоборот. Можно иметь оба. Чтобы получить NIP нужно в офисе налоговой заполнить форму NIP-7. Этот номер нужен, если нет PESEL, но есть необходимость сдавать налоговую декларацию. Например, продление карты побыту требует подтверждения уплаты налогово или отсутствия задолженности. Декларацию можно сдать имея PESEL. Без PESEL нужно использовать NIP.

UPD. В марте 2015 поступила инфа, что приняты изменения в законодательство и теперь иностранцам не выдают PESEL без крайней необходимости. Вместо него в документах просто пишут дату рождения. Если же PESEL нужен для чего-то, то нужно обосновать такую необходимость и тогда, может быть, его выдадут :)