They do have very nice diagram programs out there with network discovery ability, which will detect and "plot" your network devices for you and then you just fill in the information and clean it up so it looks "pretty".
But if you are working with tight budgets like me we need to improvise. I collect my network device information manual (ie. pad and paper) going to each device I write down the critical stats as I call it. This varies on the device.
Example:
1) Record exact model number and s/n for each and every device.
2) As applicable sumarize any added or optional features you/your company purchased/installed for the device. The idea is you need accurate information of the configuration and capabilities each device ACTUALLY has, not just what it COULD do. So if you have a Cisco Switch with an optional fiber GBIC module installed, note that in the documentation.
3) On switches/routers document any static IP addresses they have and note the IOS versions, on servers document their role, their OS, their patch level (ie. Service Pack 928192) and their IP addresses.
After data is collected, I would fire up Visio and begin the diagram process. I make it look "pretty" for both the "awe" value it has on the exec types and to make it easy for me to read.
You document the "pipes" each server takes, noting the connection speed, the duplex and any special information you feel its pertinent. The importance is don't make up stuff just to make it look nice, don't draw lines showing connections if that's not how it really connects in reality.
When someone looks at your documentation they should be able to easily figure out:
1) The topology of your network
2) The bandwidth of your network
3) The class of equipment you have
4) The roles of your servers
5) Identify special areas of your network (IE. if segments of your network are on VLANS, this should be illustrated on your documentation)
6) Security infrastructure...your firewalls, DMZ, proxy servers, gateway...all this stuff should be easy to deduce from looking at your documentation.
Personally, I also note warranty information in my documentation too.
I have my diagram and then there are follow pages as needed to summarize information.
But like I said, I'm sure places with deeper pockets use "fancy" software packages that prepare network documentation for you.