Run missions for the minor factions aligned with the major faction you're interested in. Rep from non-aligned independent factions in the same system do not count towards anything. After you gain enough rep with the minor faction(s), a Navy promotion mission will randomly appear on the bulletin board at a station in the area you've been operating in. After you complete that mission, you will receive a promotion.
After an unknown amount of rep is gained, your rep with the minor faction will no longer influence standing the major faction. You will notice this after you run X number of missions with the minor faction(s) and no Navy missions appear. When this happens, you will have to move to another system and start the rep building process over with the minor factions located there.
Note, for some players, the promotions are bugged and they are not getting promoted.
From personal experience, since I am currently a Post Captain in the Fed Navy, the best way to rank up would be to find a tight group of aligned systems and run smuggling missions between all of them. You gain rep relatively quickly, and the money is good. Just don't get caught.