So everywhere I go says that in order to upgrade your starbase level you need starbase XP. that's great and all, but I have absolutely no idea what starbase XP IS or how to get it. I know how to get starbase Engineering, Science, and Military XP, but not straight-up starbase XP. So how does this thing work anyway? Someone must know, because I keep hearing about level 3 4 and even 5 starbases out there. So what is this voodoo magic and how is it done?

You earn starbase XP from Upgrade projects, such as Construct Shipyard, or Construct Transwarp Conduit. These missions are rewarded from getting 1,000 Engineering (Industrial Fabricator), Tactical (Shipyard), and Science (Transwarp Conduit) XP. To get 1000 ENG/TAC/SCI XP, you must complete missions such as Reinforce Local Systems.

So those projects give us the XP we need? That sounds like something that should be stated either in-game or at least on the wiki.

Um...it is on wiki.

http://www.stowiki.org/Fleet_Advancement_System

"Upgrade Tiers
1,000 starbase XP (also known as fleet XP) is obtained for each upgrade project (i.e. if at 0 XP, completing a Military Tier I upgrade project will give the 1,000 Starbase XP needed to upgrade the starbase to Tier I).[7] "

Above copied directly from the wiki site.
Perhap re-review the page.

I completed my first Engineering Project and have 1,000 Engineering XP, but my Starbase is still Tier 0 with 0 Starbase XP.

Is that right? I thought the 1,000 I got from the Engineering Project would move me to Tier 1?

You have to do the project that gives Starbase XP. Look over your list of available projects and check the rewards. Some will give Starbase XP.

There are no such projects.

I have two projects available under Engineering, two under Science, and two under Military. They give Engineering XP, Science XP or Military XP. None of these give anything else.

Then you simply haven't unlocked the necessary projects yet. Keep doing those projects, and eventually you'll see it.

Once you reach enough XP in any of the tiers, you'll open up more projects, which will include ones that give Starbase XP.

First off, a quick "refamiliarization? and listing of terms:

There are 5 "project" slots - the 3 "normal" projects (for Mil/Sci/Eng XP/Provisions), the 4th is the "upgrades" slot, and the 5th is the "special projects" (where the dil-heavy fancy upgrades go and/or the "large fleet" projects...

Normally, the 4th slot cannot contain anything. However, once you get the required XP to unlock a major project (in your case, the 1000 engineering XP needed to unlock industrial fabricator), said unlocked project can be activated in the 4th slot.

That slot will also contain the actual starbase upgrade upon completion, and other unlocked projects (DOff assignment giver, bartender, tailor, etc.) as they are made available.

In my case, we went Military first. Upon hitting 1000 mil XP, the 4th slot accepted/allowed the activation of the shipyard construction project. When that was done (and the starbase/fleet XP awarded for that project), the starbase and the tactical DOff mission giver were unlocked. I (somewhat obviously) activated starbase I first, then the tactical DOff. If I don't get the Tac DOff done before hitting 1000 Sci XP, I won't be able to build my comm array then transwarp until I clear the DOff giver out (by filling all requirements, active missions cannot be cancelled/swapped out...)

For the first tier, you need 10,000 Military/Science/Engineering XP in one category. After you get 10,000 XP in one category, an upgrade project grants you 1000 Starbase XP when completed. After you finish that upgrade project, then you can upgrade your starbase to tier 1.