All OSes as far as I know have a "print queue" which seemingly buffers printed documents out to the printer in the order they were requested.
The "print queue" is the visible part of the printer service/daemon that was originally a program called SPOOL (for Simultaneous Peripheral Operations On-Line) such as for the HASP/OS360 operating system running on IBM 360 mainframes. (IMO SPOOL is one of the best acronyms coined because it is also an English word (both noun and verb) that can be used as an analogy to describe how the printer service works.)
Before network printers, I would imagine that the actual printer was sent data almost line by line from the connected machine.
True, no need for the "almost".
Now with network printers, this imagined model falls apart. I assume modern printers merely receive a postscript (or some other printing format) doc from the OS, keep it in memory and print from it.
"Line printers", or "dumb" printers that accept only plain text are essentially obsolete, having been replaced by "page printers" that accept input in some type of page description language (e.g. Postscript, PCL). Since more data than just the text for the page, that is, the complete page in PDL form, has to be sent to the printer, older interfaces such as the "Centronics" parallel port and RS-232 serial have been replaced by USB and Ethernet (wired and wireless).
Note that having an Ethernet interface and calling it a "network printer" does not mean that it is can perform like a networked "print server". The "network printer" configured in "peer-to-peer" mode actually requires a "printer driver" to be installed in every PC that wants to use that printer. That "network printer" is then actually installed as a local printer to the PC, but negotiates and uses that printer through a network connection. Print jobs to the "network printer" have to be held in the local queue just like jobs to other local printers.
Page printers are not sent the entire document (as you imagined), but a "page" at a time. Of course the "page" would be in PDL form, and could be broken up into lines and packets, depending on the transfer medium. Since these are page printers rather than printer servers, there is no mass storage (i.e. hard drive), and have to hold each "page" in local memory until it is printed. A "flow control" protocol (aka handshaking) would be in place for the PC to transmit the page fragment or page when more memory is available on the printer.
The question is, what does an OS printing queue mean if the printer can receive multiple documents?
Unless you really have a print server with mass storage (e.g. a hard disk drive), the "network printer" really cannot accept a complete or multiple documents unless they are all small enough to fit in the printer's RAM. The PC's printer queue has to be used to order & store the pending print jobs originating from the PC. Each PC on the network using that "network printer" has to contend for that shared printer. The "network printer" could maintain its own queue of job requests from all PCs, or at least which PCs are requesting service. Note that it would only know of requests, and not hold any page data (that is still on each PC) until the printer is ready to begin that job.
If you really do have a print server, then the local queue is just an intermediate step before the print job ends up on the printer server's queue.
The OS printing queue shows us nothing of what other machines are printing because it's a local buffer. So that must mean the printer has an onboard queue right? So why do we even have printing queues if we can't see what else is being printed?
Hopefully the printer has a request queue to order maintain a first-come-first-printed job list. Otherwise one PC could be crowded out by other PCs. You still need a the local queue because that is how you still submit print jobs on the local PC. Unless you have a real network print server with mass storage to hold your print job, your print job will have to reside on your local PC until it can be moved. Check with the printer's (or server's) manufacturer for a network-based app or browsing tool to query the printer's (or server's) queue/status.
How do printers print documents from multiple machines if each machine is clueless to the fact that others are printing as well?
This is a common resource allocation problem in computer science: multiple users/consumers contending for one resource. In this case (which has no complications) the printer or server can receive each request, and then prioritize them in some order. Flow control will ensure that the printer is not overloaded. Another possible solution (that simplifies the workload at the printer) would be a token-passing scheme. The PC that has received the "token" is granted use of the printer for one job. After that one job has been printed, that PC must pass the token to another PC that has jobs in its queue.
Best Answer
Self-answer: This might not be super helpful to anyone else with a similar question, but I was able to resolve this by reinstalling the drivers.
I did this by googling the printer's name - this gave a different page on Canon's site than the one my university's instructions link to, and installing that version of the driver made it work perfectly.