Well, since it's the Federation, money talks.
But for the average Joe CMDR, it means doing lots and lots of bulletin board missions and bounty hunting for the Feds. Find a nice cluster of Fed worlds and make note of the Fed sub factions who are in control. Run every mission you can between them. Of course if you're hostile or worse you'll have to dock at outposts because stations will blow you to dust. And even then they won't have many missions for you because "this faction does not trust you enough." So your best bet is to turn in a bunch of bounties for the feds. Find a neutral RES somewhere and K-scan everybody to build up a stack of Fed bounties. Turn them in at the above mentioned outposts and it will improve your rep with them. Keep doing it until your rep with them improves to neutral and you'll start getting Fed faction missions. Don't take missions that will send you places you can't deliver, i.e. to Federation stations. Outpost to outpost, or outpost to non-aligned systems.
After that, wash, rinse, repeat. You can't rebuild your rep with the whole Federation from one station. Improve your rep at one station as far as you can, then move on to the next. Getting in good with enough sub factions will eventually move your rep with the overall Federation higher. It will take a long time and a lot of work, but it can be done.
Good luck!