The recommendations so far (and they are all good ones) are for text books that cover technical material. If you are interested in the practice of OR (particularly outside the silos of academe), I'd suggest prowling the Science of Better web site, looking at issues of Interfaces, maybe Real World Operations Research: The Woolsey Papers.

The book I had as an undergraduate was "Operations Research: Applications and Algorithms" by Winston. It presented concepts using basics to start with and then got fairly sophisticated. Lots of worked examples, and covers most areas of OR.

http://www.amazon.com/Operations-Research-Applications-Algorithms-InfoTrac%C2%AE/dp/0534380581

If you're interested in approximate methods, I suggest the "Handbook of metaheuristics". It introduces most of the main concepts with chapters from some of the big names in the field, and is at a fairly introductory-tutorial level.

http://www.amazon.com/Handbook-Metaheuristics-International-Operations-Management/dp/1402072635/ref=sr_1_1?ie=UTF8&s=books&qid=1271680633&sr=1-1

If you have absolutely no background in OR I would suggest you start with the following book:

Introduction to Management Science (10th Edition) by Bernard W. Taylor

It covers almost all of the main topics (mathematical programming, simulation, production systems,...) It is truly a beginners book but simple and self paced. If you already know how to do branch and bound or you can model a system properly this book is not for you.

Nemhauser and Wolsey have an excellent book on mathematical programming you can start with that and if you are interested in the theory of mathematical programming you can go on to read Bertsimas and Tsitsiklis's book "Introduction to Mathematical Programming". Although it is named "Introduction to ..." Bertsimas's book is not an introductory book in any means. If you really like to torture yourself with the theory of polytopes I highly suggest Alexander Schrijver's book "Theory of Linear and Integer Programming". it is an amazing book but there is no examples :)

For nonlinear programming nothing beats Bazaraa's book "Nonlinear Programming: Theory and Algorithms" in terms of theory. Also "Linear and Nonlinear Programming" by Ye and Luenberger is a great reference for applications.

What exactly is your interest?

Hillier and Lieberman is my favorite big text. This book introduces most of the techniques used in Operations Research. It is often used as an undergraduate textbook.

If you're interested in urban applications, check out Urban Operations Research: Logistical and Transportation Planning Methods, by Larson and Odoni. The entire book is online. I think it assumes a certain amount a familiarity with probability theory, but no prior OR knowledge. The applications are very interesting and make the theory easier to absorb.

Other than the big texts (we use Winston, but almost any sufficiently thick book will do), I like Paul Williams Model Building in Mathematical Programming http://www.amazon.com/Model-Building-Mathematical-Programming-4th/dp/0471997889/ref=sr_1_1?ie=UTF8&s=books&qid=1258068143&sr=8-1 for its mix of theory and application.

One other way to self-study is to download software such as ILOG's OPL and work through examples (you can do the same thing with Arena or other simulation packages): it is a great way to really learn a subject.