I'm moving to poland to work and a little bit afraid of bureaucracy.
As long as you have your documents in order and are polite, the bureaucracy is nothing to be afraid of. If there is a problem, it is because it can sometimes be slow to get things approved, especially with your residency permit. But zameldowania takes five minutes, at most. Go to the Urząd Miejski on Piłsudzskiego and Zapolskiej (in the back of the building), take a number, wait in line, fill out a very short form while you are waiting, hand it to the clerk together with your rental contract and a copy of the deed you get from the owner, wait a minute while the clerk enters it into the computer and prints out a copy for you, and basta. Piece of cake!
Again, if there is a problem with that, it is usually because you end up with a landlord that doesn't want you to register, and is unwilling to give you the papers you need. Make sure that, when you are renting the apartment, you make it very clear that you will be registering and need a real official paper contract with your name and the owners name on it and a copy of the deed (wyciąg z księgi wieczyste). You can't register without them.