Welcome to France!
Congratulations on coming across this leveling guide. I am going to utilize this top section to run over some key items which will be needed for leveling. PSA If you don't like leveling, you are allowed to purchase and use a level 50 advancement from the treasure asile.
Every 10 or so levels, you should definitely change your ship. My recommendation is going from the Fallback you receive, to a Bermuda Sloop --> Corsair Xebec --> Postillion --> Stralsund --> Raa. Around the Final 40's - level 50, it will be mainly avatar combat.
If you are a role player, and enjoy the lore, I can lay out some of the mission chains.
Starting out after the tutorial, you are given a map from the dying captain.....this is the start to your characters Story Arc. These missions go throughout the leveling process and they are quite interesting. This is my main favorite line aside from the others.
Some of the other mention-able story lines are
Star Chamber/Somerset. This is a Voodoo story line started by Delilah Purcell in Port Royal. Can also be started in Jaqueme at level 45.
Dread Saints - TBD
Knights Templar - Starts in Santiago, Tortuga and Port-de-Paix. The ending of this mission is a reputation line for some cool items, and you get the Crusader Sword, best level 50 Fencing Sword.
Road to El Dorado - This chain can be started with sufficient Dutch rep in Oranjestad from Hugh. Sadly, you cannot progress towards Maarhaveen in the game, but the dialogue creates some great hype.
Pirates of the Burning Sea Official Discord.
Please make sure you join, and then ask in Discord if you ever need help, or have questions that you would like to be answered. https://discord.gg/szs29du
Prior to getting ready to venture the Open Seas to start your grind from level 1 - 50, be mindful of PvP zones (They are large red circles when you open the map) these areas are where players may attack you. When you sink inside missions, you do lose your cargo and modifications, if you had any. Always remember to ask in Nation for help if you need any!
As a noted PSA, every 5 levels, you will receive a mission from your class trainer, these missions give swords, skills and customization clothing.
These levels are pretty standard, as soon as you get into the game follow through with the tutorial. Once you have finished and you are on the docks, go ahead and find every NPC that has a green exclamation point over their head, and accept the missions they are giving you, be sure to check the magistrate offices and bars. Once you are able to accept your first Career mission, finish it, and then move onto the next port, which should be Fort Caroline.
Levels 10 - 25.
At 10 you should be around St. Augustine and Fort Caroline still. From here, you can go in a few directions, but I am going to point you in the direction to go. My go to ports for 10 - 25ish, is Port St. Joe, Pensacola and Cayo De Marquis. This is definitely the hardest grind, in my opinion, but it goes pretty quickly.
WARNING: You will have to start upgrading your ship for the higher levels, so locate someone who can help you out.
Levels 25 - 35.
At level 25, you're half way and life is pretty good. You should be somewhere around Pensacola still, if not, getting close to Biloxi missions. Biloxi is important because you are going to get 2 special items from that port which are vital. These items are "Lucy the Figurehead" and "Surgical Kit". Biloxi has quite a bit of missions to go through. Once you hit the 28 - 29 levels and you have acquired these missions, we are going to be taking a very long sail to Port Royal!
At Port Royal, you're going to be acquiring Combat Medicine, an extra resuscitation and a healing skill for your crew in avatar combat/NPC's in missions helping out. You can start this mission by going to the bar and talking to Delilah Purcell and accepting the mission called Corpi Hippocraticum. This will send you to a Doctor within the vicinity of the bar, and proceed to accept and finish all the missions he gives. They give wonderful XP, if you have XP books around this time, consider using them.
After you have finished the chain, we have some different approaches we can take at this point. We can go to Santiago and start the Knights Templar mission chain for the Crusader Sword you are level 50, which requires you to sail in between Tortuga and Santiago quite a bit. Or, we can go to La Isabella, Iguana, Tortuga or Ruddy Cove. Any of these locations will provide enough missions to get yourself to level 35 at least.
Levels 35 and up.
This is the final push home, you're almost there to 50. From here, this should theoretically be smooth sailing. We are now going to sail down to Point-a-Pitre to receive 2 more exclusive items we need for end game. These two items are Sonia's Dissertation and Junior Emergency Triage Kit, This is accepted by Edwin Codwell, the mission will send you to Rosseau. One provides speed and the other one provides crew when you take need to repair them in an instanced battle. Once you have completed these, you can begin your sail to San Marcos or you can search for more missions to accomplish in Pitre, and there are plenty. I would recommend getting to at least level 38 prior to going to San Marcos, but if you want fast levels at 35, then follow this.
Once you are at San Marcos, I heavily advise you to use XP Books otherwise you may fall short on XP. Once you're in San Marcos, accept every single mission that you find, and keep completing them until you are 100% finished here. You may wind up getting to level 41 or 42, and that is fine. I have the perfect cure to get from these hard levels to 45 very easily.
San Marcos completion - If you are not level 45 yet, don't fear. We have a few places to go which is great XP.
First up on the list Oranjestad. This beautiful Dutch port that is neutral to everyone provides some great missions that have very high XP. Start accepting and completing these, some of them require you to have a decently good ship. If you get stuck, ask in Nation for some help. Some of these missions require you to sail to St. Johns, San Juan and other locations, so be cautious about pvp zones. If you don't hit level 45 from these, dock into any port and keep finding missions to do.
Level 45 - 50. 
Sail your way to the french port called Jaqueme. The person you want to see is the person standing on the beach. These missions should be red, and that is fine. Keep doing these missions, eventually you will keep going to the Shack in the port and back. After some time, these missions will send you to Somerset which is at the north end of the map, it's an interesting port.
Once at Somerset, just keep doing these missions until you are level 50. If you get stuck, ask in Nation chat for some help, some of these missions can be quite tricky and or hard.
You are now level 50. Ask some players for tips and help on what ships to sail, and tips for Avatar combat and Ship combat.