There are three ways to get EXP: Stories (or Dailies if you want moves as well as EXP), Prize Fights, and power up sacrificing.
It is not recommended to use Power Up. Fighters are much more costly to obtain than a bit of EXP. Each fighter costs 100 Theonite, and they can be leveled for Skill Points which are valuable in powering up your main fighters.
As you get more comfortable fighting out of your FS, getting EXP will be easier. The stronger your opponents are the more EXP you'll be able to get from them.
If you want to see who's the best fighter, check out the [Skullgirls Community tier list] and see who in your collection people consider the strongest.
Even a bad gold and silver is worth using early on. Each level will raise their stats higher than a the stat raise for a lower rarity fighter, and some nodes will require you to have specific rarities.
Feel free to use your favorites, even if they aren't top tier. The entire story can be beaten with any character so long as you build them and play well.
Keep at least one strong bronze and silver around for bronze and silver Prize Fights and story nodes that limit you to certain rarities
While the ideal order to upgrade fighters varies by fighter, a popular order is Signature Ability, Moves, Attack, Defense, and Energy. To simply see if you enjoy how a fighter plays, just unlock the beginning of their SA.
Get moves to level 3 to unlock their effect. Moves that inflict bleed are excellent to have early on, as bleed deals a % of the opponent's HP which lets you fight out of your range if you can defend well.
When you have multiple moves, check the stats to see which is the best to upgrade. Attack%, Meter Gain, Defense, and HP% are the main four you want in a move, with Crit rate and Crit damage being the next most useful stats.
Leveling moves past 3 usually isn't worth it unless the stats are very good. The coin cost goes up drastically, and it can get too expensive for the benefit for only one fighter.
There's a variety of ways to earn Theonite, including Stories, Prize Fights, and Missions that refresh daily.
For Theonite missions, be realistic about what you can do and how much you want to play. That 25 Theo from Longshot might seem tempting, but it's okay to reroll it if you aren't skilled enough to pull it off. It's better to have 5 Theonite that's easy to get than 25 you can't get.
If you have a bookworm or longshot mission but you're stuck on story, replaying a node you already beat still counts towards the mission (but you will still only get 20% of the exp and coins)
Don't be afraid to try advanced and expert stories. Many of them are easier than the later basic stories, and they give a decent chunk of Theonite and coins.
Focus on premier 10+1 while starting out. While the starters aren't amazing, they're more than enough to get 1k Theo. The bonus relic has ~2x better odds for a silver and gold, so it gives you the best odds of getting a strong silver/gold early on. The silver from the 7 day bonus will also be a big help if you prefer going slow and steady.
From Monday-Saturday, you'll see three Prize Fights that feature a specific character, ranging from Bronze tier to Gold tier. Look at the modifiers and conditions for these PFs, and use these to get some extra coins and Theo as well as EXP.
On Weekends, you'll see two unique Prize Fights (PFs), Show Me Your Moves! and one that cycles between different elements. Neither of these are amazing early on, but Show Me Your Moves! can give you access to a few extra moves and coins. It's less reliable than dailies, but it's another option you can use for moves and another source of coins.
Also, look out for Medici PFs. They're by far the best way to gain coins in the game. There are two kinds: one that appears one random day for a day, and one that appears Wednesday and Thursday.