I would add...
3. completing something noteworthy
4. completing certain opportunities that promise x number of celeb points
5. someone using MC on them to give them a celeb level
See our FAQ here: http://nraas.wikispaces.com/StoryProgression%20FAQ%20Celebrities
By engaging in these activities, sims gain celeb points. After they reach a threshold, if the ratios aren't already met and the next level is not already full, they get "promoted" to the next level just like how job and skill levels work. There are also elements of celeb point depreciation over time and when...uh, shameful things happen and the public notices, but the SP Relationship add-on module is required for depreciation to work in most cases.
It's really a very sophisticated system but it gets a lot of bad press because under EA progression the points are distributed much more randomly and often the caps are so high that it seems like everyone in town is famous after a few generations, which many of us feel is kind of pointless.
Correct on the last part, what I really should have said was don't worry about the town becoming overrun because that's easier to fix/dial back than running with the entire system pretty much shut down -- except of course for those who don't want the celeb system running at all, which is fair enough too.