Documentation can mean whatever you or the client wants it to mean. I tend to be thorough. I tend to do documentation for my own benefit so I go pretty light on billable time for it.
With that in mind: I start with a log book in the server room. This is the most basic document of all.
I take a picture of the racks or of the equipment, front and back.
I use Paint.NET or the like to label important things on the pictures if I need to.
I tag important network cables and power cables somehow.
Of course I also keep track of server setup info. Literally everything I know about the environment: Installed software, number and type of disks in the arrays, what shares are in use, which accounts have higher than user rights, group/OU memberships, password policies, user passwords if I know them (several environments where I work set a single password for users that they can't change), any non-standard group policy settings, router/firewall settings...
I also collect install discs. I'm particularly interested in the server install media, the MS Office and XP install CDs, my prepped workstation image, backup software, and media for "critical" apps which are going to vary by location. I try to get those as physical media and a /apps network share but lately I've taken to keeping .ISO files on a thumb drive as well. Product keys are also a must. The discs go in a binder, in plastic sleeves with the product keys written on the disc as well as on the label of the sleeve.
Printers and copiers get location, IP address, the "map" for panel navigation, type of consumable, service tag and a copy of whatever service agreement they have. I won't work on printers.
For users and workstations, I try to at least have one page for notes. Things like "has DYMO label printer", "Shares HP1020 as HP with user across the aisle", "freaks out when icons are moved or added", "keeps installing hotbar", "needs mouse left on left side." I might take a picture if there's something really weird about their setup. The most common note I take about users is what printers they need and which one they prefer. The most common note I make about workstations is their disk/printer shares. I like to note the date the hardware started service too, when I can.
For notebooks I also collect the proper model number and serial number, what hardware was delivered with the machine, and the support phone number.
No place where I work has more than 60 computers, so that's really not too much. My documentation is usually done as simple RTF files and in most settings it's somewhere between 30 and 50 pages long. Documentation is never, ever done. You just fit it in where you can.
As much as possible, I try to keep a printed copy of my notes in a binder that's in the room with the infrastructure equipment, or at the desk of whomever is delegated to do things before calling me.