Question: I keep reading about joining a small start-up, keeping it up until it grows and then reaping the rewards.
However, the way I see it is that investors and shareholders will be reaping the rewards, while overworked employees will get a promotion at best, and they could have gotten that promotion in many other companies. Some make millions, some make 10K more per year.

Shouldn't "reaping the rewards" include seeing your equity/shares become much more valuable? If so, should one join a start-up only when equity is written in the contract?

Answer: 
There are plenty of benefits to joining a startup without equity.

1. Rapid promotion
2. Experience doing more things and having more responsibility and ability to set direction than you would at a larger shop
3. Exposure to startup people, both in your company and funders, for your next startup

None of these will make you a millionaire, however. If you want to "cash in," then yes, you want equity and you want it in writing. 

I have plenty of friends that worked for one startup or another, and even if they were "there early," when the founders sell and cash out, you don't get a handout out of the goodness of their heart - you get nothing, if you have no clear equity agreement.

So while there are reasons to work for a startup even if you don't get equity, if you are specifically looking for the cash-out part of that life, then you absolutely need a formal equity agreement - though even then, I've seen buyouts that manage to somehow screw minority equity holders, so it's no ironclad guarantee. As a deleted user mentions in his answer here, making sure you have a percentage or otherwise legally-enforceable non-dilutable claim is the only way to ensure you win.
First, just equity isn't something you should look at ever - you need a 'percentage' of the company, not just equity. Equity can be diluted which companies do all the time to get a lot of free work from employees 'hoping for a payout' - it's called 'The Golden Chains', this is what happened to the co-owner of facebook. Say FB started at 100 shares total, Mark and his partner would each of had 50 shares which if it stayed at that amount each share would be worth billions today. However, Mark tricked his partner in signing off his 'percentage' and he was just on equity so Mark raised the total shares to like 4 million and kept half of those meaning his partner had 50 shares and he had 2 million thus making his partners shares worthless.

Point is, don't trust equity unless it's a percentage of total equity created - companies trick people all the time by saying 'here is 20,000 shares for 0.001c a share in the company' and people think it looks incredibly good so they take it, are willing and get worked to the bone also while being convinced into signing something like a Non-Compete that locks them from progressing, or excelling or growing in their field and dependent on their job. Then the company adds say another 2 billion shares in which they keep all of it and you literally get maybe 0.00001c a share, are stuck in the job and dependent on them because you can't work for someone else you've built your skills in, all while keeping your salary low because of your dependence on them.

I mainly suggest that whenever a Non-Competent agreement comes in front of you you pass it up, then you are always able to negotiate more and never put your life in someone elses hands that isn't you.