Books

[Artin] Michael Artin, Algebra, Prentice-Hall

"Algebra" means linear algebra -- the study of groups, rings, modules, and vector spaces.  This is an excellent text.  I took the class this was written for (long, long ago) and I've recently read about half of the (finally!) completed book.  I find Artin's style very readable, and he covers material that's very useful in understanding relativity.  The only drawback to this book is its price, which is rather high.  If you don't have a firm grounding in algebra, and don't have a book on hand that you like, consider this one.

[Browne] John Browne, Grassmann Algebra, Incomplete draft can be found here

John Browne started to write a textbook on the algebra developed by Grassmann, but never finished it.  It's oriented toward use with a specialized Mathematica package (which was also never completed, I think).  The book was never brought to publication quality, and the programming sections are pretty irrelevant to most of us.  So why am I talking about it?
There's lots of good material in between the Mathematica stuff, and this text covers the exterior algebra in an accessible, reasonable way.  If you find differential forms difficult to understand on an intuitive level, read the first two chapters of this book!  (And you can't beat the price.)

[Burke] William L. Burke, Applied Differential Geometry, Cambridge University Press, 1985

This entertaining book presents things from a different point of view, and it can be very helpful with sharpening one's understanding of the concepts.  Burke gives many examples of applications of the mathematics he's discussing to physics, which is nice, but he tends to assume a familiarity with the physics which was, in my case, unwarranted.  Perhaps as a result of that, I found it hard to actually learn the material from this book; I found it much more useful after I'd already encountered the material in other texts.  In consequence, I'd suggest treating this as a supplement, not a primary reference.

[Einstein1] Albert Einstein, Relativity, The Special and the General Theory, a Popular Exposition, Bonanza Books, 1961

This contains a nice introduction to special relativity, and a very brief overview of general relativity.  If you're looking for a text to get started learning relativity you could do much worse than this one.  Math required is minimal.  I find Einstein's writing quite readable, even though this is a translation.  See also [Rindler].

[Einstein2] Albert Einstein et al, The Principle of Relativity, Dover, 1952

This contains a number of early papers on relativity by Einstein, Lorentz, Weyl, and Minkowski.  It's fun to read the old papers, and see how the ideas developed during the early years.  It's also cool to read these and realize you're seeing the text just the way it was published the first time; this is how it was first presented to the world.  But don't try to learn relativity from this book!  It's not a textbook and was never intended as such.  Learn it from regular textbooks or from classes; read the papers for fun.

[Herstein] I. N. Herstein, Topics in Algebra, Wiley

Don't bother.  Even though it's highly recommended by many readers, and it's a nice enough text in general, it doesn't go far enough to be of much use in learning relativity, and it's too expensive for what you get.

[Lang] Serge Lang, Algebra, revised 3rd edition, Springer

This is an advanced text.  I found it very dull, but none the less it covers a lot of worthwhile material, and gets into some things in much greater depth than [Artin].  Note, also, that Lang has written a number of texts on algebra, some more elementary than this.  In my opinion, his writing is dry, but  he certainly knows what he's talking about; you probably won't go too far wrong with any of his books.  They're much cheaper than [Artin].

[Lang2] Serge Lang, Linear Algebra, Springer

This is a less intimidating book than [Lang].  My first encounter with linear algebra was through an earlier version of this text (the Second Edition, which was published many years ago by Addison Wesley).  It covers the basics, and is available used reasonably inexpensively.  Lang is a thorough and accurate instructor, and everything you really need to know before tackling relativity seems to be present, but I find his writing painfully dull.

[MTW] Misner, Thorne and Wheeler, Gravitation, Freeman

The classic.  It weighs almost 5 pounds (in paperback!).  Its coverage is broad and deep, and the authors have tried to actually explain a lot of the concepts in an intuitive way (with pictures), rather than just presenting the math and proving the theorems using plain algebra.  Their style, though sometimes unusual, is extremely engaging.  But watch out:  This is not an introductory text, and if you already know something of tensor calculus and the rudiments of relativity before you start you'll find it much easier going.  The authors sometimes assume things are obvious, when only someone who already had a strong background in this area would find them so.  They also cover such a breadth of material that they can't help leaving loose ends, which is occasionally somewhat maddening.  In conclusion: Buy this book, study it, enjoy it, but if the going gets too rough don't hesitate to switch to something easier, such as [Schutz1].

[Rindler] Wolfgang Rindler, Introduction to Special Relativity, Oxford

I have not used this book.
This text on special relativity comes highly recommended, and I've looked over the table of contents, which looks good.  It covers the geometric viewpoint, which [Einstein1] does not.  It covers a lot of material which is typically just glossed over in general relativity texts, and looks like a valuable adjunct to the other books I've used.  I may yet buy a copy, just to fill in some of the gaps in my SR knowledge.

[Rudin] Walter Rudin, Principles of Mathematical Analysis, Second Edition, McGraw Hill

Mathematical analysis is "calculus done over, done right".  If you learned elementary calculus from Apostol you may not need anything more.   But if you're like most of us, you learned it in just 3 dimensions with some differential stuff in higher dimensions, and that's all.
Rudin covers the basics of analysis, including compact sets, limits, integration, implicit functions, and all the rest of what should be in an elementary analysis course.  It's all done in n dimensions, which is the major difference between this and elementary calculus.  If you don't know what an "open cover" is, or why "closed and bounded" is the same as "compact", you should seriously consider learning some analysis before trying too hard to understand general relativity.
Note that whether you use this text, or some other, you can safely skip the sections on Lebesgue integration and the higher-dimensional analog of Stokes' theorem.  Lebesgue theory is largely inapplicable in the real world, and Stokes' theorem is probably more easily learned from a more advanced differential geometry text.

[Schutz1] Bernard F. Schutz, A first course in general relativity, Cambridge University Press

Excellent book!  Buy it!
Schutz follows the same approach that [MTW] use but his coverage is much, much narrower than theirs.  His target audience is undergraduates, and that makes a big difference to how he presents the material.  He deals with special relativity, general relativity, and that's all (no electrodynamics, no miscellaneous differential geometry thrown in for fun, no extras).  His writing is pleasant, his proofs are accessible, his explanations are mostly comprehensible.  He does a nice job of explaining special relativity, as well (but you will still find the going a lot easier if you've already learned special relativity from a simpler book, such as [Einstein1]).  And the book is small and light enough to carry along on the bus, to the beach, or anyplace else, which may be significant when you consider that any general relativity text, even this one, is likely to take you at least a year to read!

[Spivak] Michael Spivak, Calculus on Manifolds, Benjamin, 1965

This book is a classic.  It's a monograph on differentiation and integration theory on manifolds.  Most of the text is devoted to developing the theory of differential forms, and in the last couple chapters Spivak presents Stokes' theorem and the classical theorems which are its corollaries.
I have a couple of problems with this text.  Spivak, for all that his writing is very clear and engaging, makes little attempt to explain what a differential form means, nor does he attempt to show any intuitive meaning for the exterior derivative of a differential form.  Stokes' theorem, when properly presented, is intuitively obvious -- even in n dimensions.  When I first read this book, however, I was left struggling to figure out what it was about.  The whole statement of the theorem fits on one line and uses only 9 symbols, but their significance was largely lost on me.
My other objection is that Spivak tried too hard to keep it elementary.  He treats only manifolds which are explicitly embedded in Rⁿ.  That should simplify things, and in this area, any simplification is to be applauded.  However, the consequence is that he seems to have a lot of useless mechanism lying around doing nothing, because nearly all of what he's talking about is just Euclidean space.  I also found it substantially harder to keep track of which maps were going in which direction, because so much of the mapping that's going on seems superfluous, and because every map is from Rⁿ to R^m.  If the theory is done on abstract manifolds, instead, none of the maps are superfluous, and it's easier to see the significance of what's being done ... or, anyway, that's how it seemed to me.
If you want to understand differential forms, you should take a peek at [Browne] before you dive into calculus on manifolds.

[Symon] Keith R. Symon, Mechanics, 3rd edition, Addison-Wesley

This is largely unrelated to relativity.  It's a standard "intermediate-level" mechanics text.  If you would like to learn something about the Lagrangian formulation of mechanics, which isn't typically taught until the junior year in college, this may be of use.  The first half-dozen chapters cover the Newtonian formulation (f=ma) and then he gets into the more advanced stuff.  The drawback:  I found this text painfully dull.  Goldstein is more advanced and consequently harder to understand, but Goldstein's writing is less soporific, in my opinion.

[Wald] Robert M. Wald,  General Relativity, University of Chicago Press, 1984

This is a really fine text.  The treatment is very "modern", the coverage is very deep.  His viewpoint is very abstract, which means he doesn't specialize needlessly and hence gloss over aspects of the subject matter.  He includes a review of differential geometry in the appendices which is also worthwhile.  But beware: This book is very dense.  Learn differential geometry and general relativity first, then tackle this book.

[Warner] Frank W. Warner, Foundations of Differentiable Manifolds and Lie Groups, Scott, Foresman, 1971

This is one of the references cited by [Wald].  It contains a very nice introduction to the theory of differentiable manifolds.
Drawback:  That nice introduction is in the first chapter; after that he hits the accelerator and it's bye, bye.  The rest of the text is very dense.  (But it's a skinny book...)
However, even if all you ever read is the first two chapters, this could still be a worthwhile book, because it presents the "modern" theory of differentiable manifolds in a thorough, more or less comprehensible way.

[WarnerS] Seth Warner, Modern Algebra, Dover

I have not used this book.
I've seen this recommended as a good place to start, and I've looked over the table of contents.  It certainly covers all the topics that are really needed.  Reviews I've seen have been mixed; some like it and find it useful, some say it's too thick and leaves too much in the exercises.  But one thing's certain:  It's cheaper than dirt.  If you want an inexpensive intro to algebra, you can pick up a used copy for about ten bucks.  If you don't like it, you haven't lost much!