As stated by many, Wiseman's SAS book is a must-have. As well as the U.S. Air Force 64-4.

A book that I rarely (if ever) see mentioned though is Richard Graves's Bushcraft. It was the first book written with the title Bushcraft (not to take anything away from Mors Kochanski -- his book is phenomenal as well) but I learned a lot from Richard Graves's book. Highly recommended. And can still be found on Amazon for five dollars!!