Last updated September 9th, 2020.
Here's my list of recommended materials for math competitions, along with some thoughts and advice on how to prepare for the AMCs and AIME. Especially for beginning students, I must stress the following: Don't let your past self get in the way of your future self, and don't be a completionist. 
Alcumus - Online math learning tool. Good for absolute newbies.
Exploring Euclidean Geometry - My geometry book. It assumes basically no knowledge of geometry, so newbies can learn foundation concisely and thoroughly.
Similar Triangles - Some relatively difficult similar triangle questions.
Angle Chasing - Assumes knowledge of basic knowledge, including Inscribed Angle.
Art of Problem Solving, Volume 1 - Good way to learn the basics of geometry. I personally only used the book to fill in geometry gaps and barely read the rest of it.
MAST - My own AIME training program. This program is my answer to the question "How do you do well on the AIME," and it answers far better than I can.
Art of Problem Solving, Volume 2 - First math competition book I got my hands on. I used to swear by this book. This is on the easier side and gifted middle schoolers may consider skipping Volume 1 entirely.
AIME-like Problems - A set of questions that feel similar to the AIME but were not actually on the AIME.
Proofs in Competition Math - Fairly high-level look into several branches of math. A good portion of the content is applicable to AIME, but a good portion of it is not directly applicable as well.
Polynomials in the AIME - Fairly comprehensive guide by naman12. 
Telescoping - My Telescoping handout. Very early version of a MAST Handout.
Eyed's Recursion Handout - Good introduction to Sequences in the AIME. 
Common AIME Geometry Gems - Problems that you're likely to encounter in your standard "geometry AIME class."
NT Abridged - Very brief handout on divisibility and the three modular arithmetic theorems.
Chapter N Section T - Large collaborative handout covering many NT topics. Also includes induction and pidgeonhole for some reason.
These are resources that I haven't really used that thoroughly. But they're almost universally mentioned by other people in response to "where to start" threads, so I figure it does more good than harm to have them here.
AoPS Introductory Textbooks - A lot of people swear by these. I recommend against treating them as the holy grail, but these are very good books. 
AIME Handout - Very brief exposition of topics followed by a plethora of AIME problems. 
Justin Stevens - A gentle introduction to Olympiad Number Theory.  Requires no previous knowledge.
Naoki Sato - Olympiad Number Theory condensed. Should be used as a supplement.
References to other people's websites that I've found useful or enlightening. In practice, you'll probably be fine if you just look through here to start and completely ignore my website.
web.evanchen.cc - IMO gold medalist (2014) and current olympiad coach. Materials are on the hard side. His posts about math pedagogy are enlightening. 
paulgraham.com/articles.html - Essays from computer scientist Paul Graham. While his content isn't directly related to math competitions, his ides about work are incredibly helpful.
davidaltizio.web.illinois.edu - David Altizio's website. Mostly has AIME stuff but there are some introductory handouts too.
numbertheoryguy.com - Justin Steven's website. Mostly AIME-level and Olympiad-level Number Theory stuff.
TheBeautyofMath - Youtube channel run by AoPS user IceMatrix. He has a lot of video solutions to past AMC problems. He has a video on preparing for the AMC. I strongly believe that this should be treated as a recommended reading list rather than a to-do list.
This is roughly what I believe people who're completely new to math competitions should start with. I highly recommend reading Diminishing Returns for one of the most common mistakes and how to avoid it, and Escape Velocity so you understand why learning math is so hard, and how to combat some ingrained bad habits. Important disclaimer: I am only one person. Learning is really just the integration and synthesis of different useful perspectives.  So listen to what other contestants say too, and don't follow any list religiously (even your own).
First and foremost, I'd like to welcome you to the math competition scene. The problems are hard and there are times you'll feel completely disconnected. But I assure you the experience is worth it. Math is also a social experience in two regards: Math is much more fun if you're doing it with some sort of community, and it'll be a lot harder to improve and stay motivated if you don't have a community. So if you don't have smart friends, now is the time to change that. Fortunately, due to the internet, anyone can become part of a community. There's really no reason to not reach out for help and support, so don't be shy!
One of the most important skills that you need to develop is to be able to tell when material is working for you and when it isn't. If you know this you'll be halfway there. A really easy way to tell whether you need to read part of a book or a handout is by first looking at the problems. If you have no idea how to do the problems, you should read the theory thoroughly. If you can do some problems but not others and you think it's because of knowledge gaps, you can keep doing the problems while using the textbook as a reference material. If you can't do some of the problems because of an intuition gap, do the problems you can in order to close it.  If you can do most the problems, you either have the choice of skipping the section entirely or just doing the problems without reading anything.
Depending on how good you are, I suggest starting with Alcumus. You'll need to make an Art of Problem Solving account. While there are some successful people who don't use AoPS, I guarantee you that 1) the vast majority do use AoPS and 2) the ones that don't get away with it because they can contact a lot of other smart people through other means. I think it's strictly unoptimal not to use it, at least when you're beginning. 
But I really suggest not starting with Alcumus if you can get away with it. Your benchmark should be the AMC 10 (or AMC 12 for any late bloomers) . To this effect you can just solve problems, look for stuff you don't know, and learn it. At the beginning there will be a lot of things you don't know, so any well-written book will teach you most of what you need to know. I think it's really hard to actually consistently get yourself to do math competitions under timed competitions and you only risk burnout if you do this. Practicing a competition under timed conditions is a bit like salt: You can't get away with none of it, but it's really not the main substance. 
Especially for younger students, geometry is often the hardest subject to learn because it's so theory based.  That's why the area I focused most for my material recommendations was geometry - most people can actually just get away with doing pretty much anything for the other three subjects. Geometry actually requires some care to learn and is probably the hardest to write about. I would say maybe 80 to 90 percent of the material you try to learn geometry with will not be incredibly useful, so be willing to learn it in a piecemeal fashion.
I was asked why I viewed Alcumus negatively on this essay by a reader, and I think the answer is somewhat informative so I will leave it here.
The historical reason that this essay frowns on Alcumus because the essay was originally written for high schoolers trying to figure out how to start.  Once I made the audience more broad, I figured that it did not do harm to provide a more contrarian view of Alcumus to some middle schoolers, because I know that at least when I was younger I had an inflated opinion of Alcumus. In fact "Escape Velocity" was originally part of it, and I only separated it because I had enough things to say to make a separate essay and "Where to Start?" was getting very long.
On a positive note, if you need the motivation to actually do some problems and you haven't built up some intrinsic reason to do so yet, then Alcumus is really good at doing that for you.
 This is the short version of my essay Diminishing Returns.
 The effects of making these two mistakes is the same. But the way to tell people about them is slightly different. This slight difference may actually have significant effects.
 He's also a grader for MAST!
 The corresponding MAST unit is Sequences in the AIME.
 I'm going to be honest: The only Introduction book I've even read a page of is the Introduction to Geometry book, and I don't actually particularly like it. It feels designed to make you read it really slowly in an artificial way.
 I haven't extensively used it, but as far as I can tell this resource is pretty conservative with what it teaches. My main criticism is that it almost feels sheltered.
 This does not come at the expense at thoroughness.
 I might go as far to say that would be the most useful part of his website for the vast majority of people.
 The qualifier "useful" is very important. When your math teacher tells you that you need to explain so-and-so to your classmates instead of just being certain you're right, they're insisting you synthesize useless perspectives.
 At some point you'll probably feel the need to read the section. It's much better to read something in the mindset of "okay, this is what it takes to click" as opposed to "I suppose I am going to read this because I have some vague feeling I am supposed to."
 You might take a break from or leave AoPS once you've gotten a hold of things. Given the current state the fora are in, this may be strictly optimal.
 Don't overfocus on the AMCs! This is just a rough benchmark. When you've gotten a better internal benchmark you should definitely use that instead.
 Don't worry about "running out of mock tests." I'll share a secret with you: Basically the only official tests that are remotely similar to what you might see in the future are from the last three years. AoPS Mock Contests has a pretty large supply of good, accurateish mocks. Just worry about getting better at math, because 1) problems are kind of limitless and 2) saving stuff for your future self is bad because you currently have bad taste. Future you agrees. (If future you doesn't, that's a bigger issue.)
 This is true in Olympiad Geometry too - just knowing configurations and theorems well can get you pretty far.
 I think middle schoolers usually have enough to start on their own anyway.