Here is what I do, before recruiting anyone take on a few small bands of looters to get used to combat then decide what kind of weapons you want to use (bows, swords, etc) and start leveling that up. Sell all loot that isn't as good as your stuff, but take what you get that is better.
After you get a thousand or so gold, look in taverns for mercenaries. The best infantry would be Hired Blades, but they are expensive (worth the cost though). You may want to go with Mecenary Horseman or Merc Cavalry since in the M&B world cavalry are key to victory.
Then go pick on some mid-level bandits like Forest Bandits or Tundra Bandits. Avoid Steppe Bandits, those horse archers can be VERY annoying to beat. Also look out for Sea Raiders, they are quite tough infantry.
After you get some decent gear, go take on some Sea Raiders since they have the best loot. Building yourself up like this gives you a chance to figure out what weapons work for you while leveling up. You also increase your reknown.
Fight in a tournament every now and then if you feel confident. Be warned, you may get screwed over so save before hand and make sure you don't choose to auto-save when you are making your character. The reward maxes at around 4000 with max bets every round, so the profit isn't amazing. Quests from Village Elders, Guild Masters, and faction lords also don't have overly high rewards, so I stick to looting bandits and deserters.
Once you get yourself built up enough, it is time to choose a faction and the real gameplay begins. Get friendly with a faction of your choice (I normally go with Swadia because the Swadian Knights are absolute beasts in open field fights and in sieges, but they are hard to get), and ask to join them. You get a town to manage and can siege enemy stuff. Look for lightly guarded castles and small warparties until you get built up enough to take on larger warbands and better defended castles.
Castles that you need siege towers for require a VERY long time investment so be sure to have enough food. Also, note that warriors don't like fighting their own faction, so don't try using Vaeger infantry against Vaeger armies. If you get enemy units, use them as garrison troops so morale won't effect them.
I hope this wall of text helps.