I am very lucky to have located a relative that had a version of a birth certificate along with working papers of my grandfather when he lived in Poland. My grandfather was born in Chelmek, Poland. I have the complete date of birth, and his father's first name. I also have working papers placing him in the mining industry in Libiaz, Poland in the very early 1900's. The working papers have the name of the company and the Mining Union he belonged to in Libiaz, Poland.
I am planning on going to Poland to visit Chelmek in Sept of 2008. I have located our last name, Majcherek, to still be current in Chelmek and Libiaz. What would my next step be in locating family.
Before travelling try and contact the local parish church and archives. It will take some time to locate living relatives, if there are any still living there, by which time you would have already left. An alternative to this would be to get a private researcher to do this for you.