I've wiki'd this post - could those with sufficient rep add in items to it.
System administration, general usage books
Nemeth et. al, Linux System Administration
The Armadillo book, as mentioned by Bill The Lizard below.
Anything by Mark Sobell. He does a sort of theme-and-variations for various flavours of unix, so pick the book most appropriate to the environment in hand. The books are quite good. One of his was a prescribed text when I did my B.Sc.
Stevens' TCP/IP illustrated, vol. 1: The Protocols for a comprehensive run down on how TCP/IP works in detail.
I've never read this particular book, but many people here are recommending Unix Power Tools as mentioned by Hortitude.
Anything by the late W. Richard Stevens, in particular Advanced Programming in the Unix Environment and Unix Network Programming Vol. 1 and vol. 2
Various classic c/unix books, such as The Unix Programming Environment, Advanced Unix Programming, Programming Pearls and of course K&R. The C/Unix books tend to go into the underlying architecture, and will give a fair degree of insight that's relevant across the board - these are the underlying mechanisms within the system. Anyone trying to do system-level programming (basically anything using system services, no matter what the language) will find a grounding in this to be beneficial.
Specific tools (e.g. Sendmail)
Various of the books from O'Reilly and other publishers cover specific topics. Some of the key ones are:
The Bat book on sendmail - if you have occasion to experience the joys of working with sendmail.cf. If you have a choice on MTA, postfix or qmail are somewhat easier to work with (I've been using postfix since about 2000). O'reilly publish guides to both of them.
Some classic works on perl: the Camel and Llama books (the latter written by none other than Randal Schwartz).
Sed and awk. Not sure what the critters on the cover are. My copy went south a while ago. While on the subject of this, Mastering Regular Expressions has also gotten a mention here and is a good book on the subject.
Samba. The hornbill (?) book covers this; there is also quite a lot of on-line documentation.
NFS/NIS for those using or maintaining unix or linux clients.
Some of these books have been in print for quite a while and are still relevant. Consequently they are also often available secondhand at much less than list price. Amazon marketplace is a good place to look for such items. It's quite a good way to do a shotgun approach to topics like this for not much money.
As an example, in New Zealand technical books are usurously expensive due to a weak kiwi peso (as the $NZ is affectionately known in expat circles) and a tortuously long supply chain. You could spend 20% of a week's after-tax pay for a starting graduate on a single book. When I was living there just out of university I used this type of market a lot, often buying books for 1/4 of their list price - including the cost of shipping to New Zealand. If you're not living in a location with tier-1 incomes I recommend this.
E-Books and on-line resources (thanks to israkir for reminding me):
The Linux Documentation project (www.tldp.org), has many specific topic guides known as HowTos that also often concern third party OSS tools and will be relevant to other Unix variants. It also has a series of FAQ's and guides.
Unix Guru's Universe is a collection of unix resources with a somewhat more old-school flavour.
Google. There are many, many unix and linux resources on the web. Search strings like unix commands or learn unix will turn up any amount of online resources.
Safari. This is a subscription service, but you can search the texts of quite a large number of books. I can recommend this as I've used it. They also do site licences for corporate customers.
Some of the philosophy of Unix:
The Art of UNIX Programming by E S Raymond (available online and in print).
The Practice of Programming by B W Kernighan and R Pike.
I recommend the Armadillo book from O'Reilly for command line administration and shell scripting.