Possibly the most important task you have when starting with a new company is to check the existing documentation.  I personally consider it a matter of professional pride to ensure all systems are fully documented and a hand-over pack is left in the safe for however comes after me, but not everyone is so inclined.

At least the following should exist, or be created by you within days of starting :

1. Key Passwords, such as the domain adminstrator, service accounts for SQL or Exchange, admin passwords for 3rd party systems etc.  How these are stored is up to you, I always include a reguarly updated "cheat-sheet" kept in the safe (I'm assuming here you have a dedicated IT safe, you don't want to be sharing a safe with accounting or some other department).
2. IP Addresses.  Whilst most clients will probably be DHCP, servers and routers won't be.  You should have notes of the IP addresses and an overview of the hardware.  Visio is great for producing simple overview network diagrams which can cover all this information.
3. License details.  License management can be difficult at the best of times, and without adequate documentation you open your employer up to potential legal difficulties if you can't prove you have the pre-requisite licenses for all the software you use.
4. Hardware log.  I always keep a list of all hardware; client, server and network.  Whilst this might seem like a chore initially, it's pretty easy to keep up to date and can be invaluable when planning upgrades or justifying new hardware to management.

What else do you document?