Networking 101 | Document everything
Documentation is you friend. In fact it is so important that you should have you documentation done before you begin, and check it oven to ensure it's accuracy.
Visio is your friend
Documentation, Documentation, Documentation, did I say Documentation?
Microsoft Visio is a must if you are a Windows user. If not check out Dia, it is an open source Visio-like app. Make lots of diagrams, where the network is, where you want it to be, the the steps to get there.
Take lots of photographs
A picture is worth a thousand words.
When making your plans take lots of photographs of the current environment. This will come in handy during the planing stage. Trying to explain to someone how bad a network closet is isn't nearly as effective as showing them. These don't need to be from a fancy camera. I've found that Blackberry's and iPhone's cameras are sufficient, however, flash is needed a lot and may drain your battery fast.
Layout your entire plan before hand
Yes, your design will change. No plan ever survives meeting the enemy but that is ok. At least you can see what changed and why, and then communicate with others.
Keep in mind that you are not the only one
No matter how big or small the job is, someone else will eventually have to figure out what you did and why. So please just print out the thing put it in an sheet protector and tape to the door.