As with anything, getting good at math contests is basically about practice, and to put in the practice time one needs motivation.
If you've decided you really do want to be working on math contests, below are my suggestions on how to improve. Most of the tips apply to all math contests; towards the end there are some things specific to math olympiads.
The main message is to do more problems. Find old copies of the contest you are preparing for. Try to make sure you have the solutions, not just the problems and answers. Books of old math contests (especially if you are talking about AMCs, AIMEs, olympiads, or Mandelbrot) are definitely worth the money. Some other sources are ICTM and HMMT.
Make sure you're working on problems at an appropriate level, otherwise you will not improve. If you're getting nearly all the problems you try right, you should try harder problems. If you're not getting any of the problems you try, you should try easier problems. (There is an exception though: if you expect to qualify for an olympiad, you should work on olympiad problems, even if you can't seem to get any of them right. That's the way it goes at first. But pick the easier olympiad problems. See below.)
Now do a lot of old contests. Doing a contest should be a three-step process:
Take the test. There are two ways to do this. One way is to take it under "test conditions", meaning you time yourself, solve all the problems all the way out, don't use a calculator, don't look at the solutions, don't ask for help, etc. That's a good thing to do now and then to get a sense of your time management and estimate what you're likely to get on the real test.
The other way to do it, which is probably the best thing to do for most of your studying efforts (especially at AIME level and beyond), is not to time yourself (just take as much time as you need) and to only work on a problem until you see how to finish. (In other words, you don't need to compute the actual answer, just be sure you know how to do so.)
In some cases you may want to work on partial contests. Let's say you're working on the AMC12. It's a 25-question, 75 minute contest. Let's say you get the first 10 questions right every single time, and it always takes you 20 minutes. Then you may want to try starting at number 11 (and give yourself 55 minutes, if you're timing yourself). Some amount of drill is good, but if you consider a certain class of problems easy, don't drill on them to the point of boredom.
You should work on the problems until you have solved or gotten stuck on all of them. Feel free to take a break from one problem to work on another. Most students give up too easy, don't let that be you. And don't just stare at the page: use your problem-solving knowhow. What techniques typically apply to this sort of problem? Have you tried them all? Have you tried looking at a simpler version of the same problem? Does this problem remind you of anything? Make sure you really have run out of ideas before you give up. Have you made all the interesting observations that deserve to be made about the problem?
Here is a way to know whether you're giving up too quickly, or (less likely) not giving up quickly enough. If you give up and read the solution and say "oh, there's no way I could have got that, because I've never seen technique X before", or you just have no idea what the solution is doing, then you were right to give up when you did. But if you read the solution and don't get that feeling, you gave up too soon.
When puzzling over a problem, don't waste time on a time-consuming approach if you think there's probably a better way. If you really can't find the better way, read the solution rather than using an inferior method.
If you are taking the test under test conditions, make a note of what you had accomplished when time ran out, so you can grade yourself later, but then continue working until you're stuck. You're not done when the time runs out!
One more thing: before checking the official answers, spend some time checking your work. Exactly how much effort to put into this is up to you, but the goal is for you to be catching most of your mistakes yourself. Not knowing how to do a problem is fine, but thinking you do when you don't will get you in trouble! If you do make an error, try to figure out how it happened and how to avoid that error in the future.
Grade your test and read the solutions for everything you couldn't get. Mark the solutions you don't understand and ask a friend or teacher later. Also read the solutions for problems you solved correctly but for which you suspect there is a better/faster method. When reading solutions, there are two important points to keep in mind:
Don't just read the solution, extract the trick(s). Usually there are one or two new tricks or insights embedded in a solution, and the rest is just stuff you could have figured out yourself. Solutions don't come out and tell you what the trick was. You have to figure it out. What was the first thing in the solution that you yourself didn't think of trying? Can you see why they did that and how you might have thought of it? If not, try asking a friend or teacher to see if they have some intuition on the matter.
When you've found the main insight(s) of a solution, make a note to come back and try the problem again later, to test whether you can remember the trick. You may want to write the problem and the trick (or even the full solution) down in a notebook. (Everyone should have a math notebook. Use it to write down important concepts, theorems, etc. as you encounter them.) The act of writing things down reinforces your memory.
You don't need to read every word of a solution. If you can extract the trick without reading the whole thing, don't waste your time. Instead, try the problem again to see if you extracted the right trick.
Follow up. Periodically go over the tricks you've learned and test that you can still solve problems you studied a while ago. When you have a chance, ask teachers to clarify solutions you couldn't understand, define terms you don't know, or tell you "how you would have thought of that." Teachers love questions like this (well, the good ones anyway).
Now that we've covered the main point, which is to do more problems, some other advice:
If you have one or two days left before a test, the best thing you can do for yourself is to get enough sleep. Don't wake up tired on test day; you will likely be tired while taking the test, even if you don't notice!
Many students struggle with contest problems because their mathematical foundation is not strong enough. If there's anything from regular high school math (up to precalculus) that you don't know by heart, fix that.
There are good problem-solving books out there which will teach you tricks and techniques you would otherwise have to learn by word of mouth or by reading solutions. For example, the Art of Problem Solving book collection covers pretty much every topic that appears on pre-olympiad contests (see the section about them lower down on this page). Engel's Problem Solving Strategies and various books by Titu Andreescu and/or Zuming Feng are good for olympiad contests. (This is not an exhaustive list.) But note that while these books teach you the necessary "background knowledge", just reading them isn't enough; there is no substitute for studying old problems and solutions.
If your problem seems to be time rather than knowledge (i.e. you know how to do the problems on a particular contest, and you work as fast as you can, but you never finish in time), you probably don't know the fastest methods. There are a few things you can do about this:
By the way, if you're wondering about how fast is "fast enough", you can see here.
Do you make a lot of stupid mistakes? Read this essay by Richard Rusczyk: Stop Making Stupid Mistakes.
Here are the main things I tell students:
Study skills: see here!
Some students are tempted to say, "I'm getting all A's, my study skills are great!", but that's not necessarily the case. The point of study skills is not just to perform well academically but to do it without spending too much time or creating too much stress. That leaves you in a position to get sufficient sleep, exercise, and occasionally enjoy life!
On a larger theme, all the general advice you've heard a million times is correct and will improve your contest performance (among other things!): stay organized, plan your day, exercise, eat right, make time to relax, get enough sleep, work before you play, do the hardest task first when you sit down to work, don't overload your schedule with too many different things (lest you become a jack of all trades and master of none), etc. This whole topic of "life skills" is something schools don't really teach (maybe because you can't put it on a test), so make a conscious effort to go out and learn about it yourself.
The AoPS books are a good starting point for preparing for math contests like the AMCs/AIME.
To do well on these contests, you will need to know almost all the ideas in the AoPS books (though there are a few things here and there, especially in the Intermediate Counting book, that don't appear until the olympiad level). Conversely, the AoPS books contain pretty much all the necessary background knowledge for math contests (pre-USAMO level). (But remember, just having the background knowledge is not enough to do well on contests, you also need problem-solving skills, which are built through practice, puzzling things out, studying solutions, working with a teacher, etc.)
Note that most AoPS books (with the notable exceptions of the Intermediate Counting book and AoPS Volume 2) cover similar ground to an ordinary middle/high school math curriculum. If you have already learned (well!) the material a given AoPS book/chapter covers, it's probably not necessary to read it. If you haven't yet learned it, though, AoPS is a good choice, because it will get you thinking about harder problems than you otherwise would. You may want to supplement AoPS with more traditional textbooks as well, just to make sure you're getting sufficient drill (traditional textbooks have more of that).
Here is a summary of the AoPS books that will help you figure out which ones you might want to study.
|Book||How much of this is in typical high school math texts (roughly)?|
|Introduction to Algebra||100%|
|Introduction to Counting & Probability||50%|
|Introduction to Geometry||90%|
|Introduction to Number Theory||70%|
|Intermediate Counting & Probability||0%||Note: Chapters 5, 14, 15 don't really appear on contests until olympiads.|
|Calculus||90%||Note: Not relevant for contests.|
|AoPS Volume 1||90%|
|AoPS Volume 2||40%|
|Competition Math for Middle School||90%|
Here is some advice specific to practicing for olympiads (this is mainly aimed at students who are new to olympiads):
Understand that olympiads are not representative of "real math" as practiced by professional mathematicians, even though they look rather similar to what mathematicians do. Olympiad problems are contrived so as to have clever solutions, in much the same way that crossword puzzles are contrived; real research is not like that. Also, the olympiad "curriculum" is quite different from what mathematicians care about. It only covers "high-school level" topics (albeit in great depth), and most mathematicians aren't especially interested in these topics, or even especially knowledgeable about them. So there's no particular reason you should be studying the olympiad curriculum rather than group theory or topology or whatever else catches your fancy. The point is: olympiads are not the "gateway to math", and you shouldn't feel any pressure to get good at them if you're not intrinsically interested. If you are intrinsically interested, read on.
Read a lot of solutions. Learning to solve olympiad-level problems is hard, because one needs to be exposed to a large body of tricks and techniques before one can make much headway on them. These tricks are not taught in school, are not the same ones that appear on easier math contests, and you are very unlikely to discover them yourself. Therefore, you will need to acquire them by reading (or from a teacher who knows them). Also, while the basic tricks are often written down explicitly in book form (for example in Engel), most tricks are not, so there is no substitute for exposing yourself to a lot of actual solutions.
Because olympiad tricks are obscure, the first time you try olympiad problems (and maybe the 20th time), you will do badly. That's normal and doesn't mean you're not smart enough for math olympiads. Don't get discouraged. Just keep reading solutions and figuring out the tricks. These tricks do exist and are learnable. Again, you need to read a lot of solutions before you will be able to construct them yourself. This is true of olympiads much more so than the easier contests. It also pays to be pretty aggressive in extracting general tricks: try not to extract merely the trick for the particular problem you're reading, but the whole way of thinking that led the solver to find it.
As for where to find solutions, many of them are online. Also, the IMO Compendium and pretty much any book by Titu Andreescu and/or Zuming Feng is full of nice solutions.
If you're not sure what does or doesn't constitute a valid proof, write up your best shot and give it to a teacher to evaluate.
Personally I don't think it's too important to time yourself when practicing.
When you are starting, start with USAJMOs, USAMO numbers 1 and 4, and olympiads from countries where they run easier. Skip the 3s and 6s until you can get the easier ones (unless they look interesting, in which case, by all means try them).
Know when to quit. This is very important. If you are frustrated with a problem or have run out of ideas, stop working on it. Either read the solution and extract the trick, or put the problem aside and come back the next day. If you find yourself doing lots of tedious algebra, it's probably not the intended solution. Unless you really feel enthusiastic about continuing, stop and look for a better way (or read the solution). Don't feel bad about giving up and reading solutions, even if you do it for the first 50 problems you try. And don't feel bad about giving up fast. If you look at a problem and after five minutes have no clue whatsoever what to do, go ahead and read the solution. You shouldn't give up until you run out of promising ideas, but sometimes it only takes you a minute to conclude you have no promising ideas. (In such cases you may want to read the first few sentences of the solution and then give it another shot.)
A couple very general techniques on olympiad problems:
Olympiad problems are often solved by guessing: you guess about what tactic to apply, what cases to look at, etc. They give you 1.5 hours per problem so that you have time to make a lot of guesses. It's ok if most of them are wrong. Even if you get good at olympiad problems, you will still be making wrong guesses before you make the right guess. Don't expect that there is something about the problem which tells you precisely how to proceed. At best there will be something about the problem which tells you a few possibilities for how to proceed.
Olympiad problems often involve working forwards. This can be an unfamiliar idea to people who have gotten very good at lower-level math contests. On many lower-level math contest problems, you work backwards: I want X, to get it I can use Y, to get Y I can use Z, so let's get Z. On olympiad problems, you usually don't know at first what intermediate steps to shoot for. You have to try playing with some examples and looking for patterns. If you see a pattern, try to prove it. It might help later. Or it might not. The point is that you're working from things you know to generate more things you know, rather than merely working backwards from things you want to generate more things you want. Hopefully the "haves" and "wants" meet in the middle.
To summarize: do a lot of practice problems, give up when you're out of promising ideas, and always read the solution afterwards (and make sure you've fully understood it). If the solution used an idea that you were familiar with, but you didn't think to use it, ask yourself what might have tipped you off.