The usual question I ask when someone asks "What key is this in?" is "Why do you care? What do you want to do with that information?" In some repertoires, like a lot of "classical" music, it's very clear what constitutes "being in a key." But even there, there can be significant ambiguity. (I discussed some of the issues about interpreting an ambiguous key in an answer here.)
The piece in this question doesn't follow the standard harmony of "classical" music, though. It has a different harmonic vocabulary. Trying to shoehorn it into some other classification system according to some arbitrary ranking or rules is an exercise often more about the priorities of the particular analyst than about how the music actually works.
To spare you from the rest of my thoughts (if you don't want to read the extended discussion below), if you forced me to classify this piece according to standard diatonic modes, I guess I'd say B♭ Mixolydian, with some chromaticism (particularly the repeated extended use of the D♭ harmony). That accurately reflects the predominant scale and the fact that B♭ seems to be a local "center" that the piece keeps coming back to.
But what does it mean to be "in B♭ Mixolydian" other than the fact that there's an A♭ instead of an A♮? Is that a useful classification? It doesn't necessarily tell us a lot about how the harmony of this piece works. As I discussed in the linked answer above, a piece of music is often like a "world" that you enter into. As you listen to the piece, you learn the "language" of that world, including the harmonic language.
A piece in B♭ major in the stereotypical classical sense will harmonic progressions that you could think of in a flowchart. Most of the flow keeps going back to B♭. Specifically, a lot of harmony will go through F major (or F7) back to B♭ major. You'll see a lot of things like B♭-E♭-F-B♭ progressions, known as I-IV-V-I. Or you might substitute C minor in and see something like I-ii-V-I. And you'll also see cycles like I-IV-I and a possibly other things.
That's absolutely not the harmonic flowchart of this piece. As noted in the question, the most common harmonic cycle in this piece is I-♭VII-I, or B♭-A♭-B♭. There's no real use of the dominant F major that I heard listening through once.
What else do we have? Mostly a bunch of E♭ major chords and also quite a bit of D♭ major. These are also two major chords a whole step apart, like B♭ and A♭.
There is a kind of harmonic backdrop for a piece like this. It's a cycle of fifths going toward the subdominant side of the circle of fifths (B♭-E♭-A♭-D♭). Typically classical harmony in major keys tends to be rather dominant-side "heavy," with V and V/V appearing a lot. There are often even longer cycles of roots of descending fifths, like iii-vi-ii-V-I.
But other musical styles (e.g., some gospel influenced music) tends to go the other direction, with IV and IV/IV, and in this case even IV/IV/IV (which is one way of interpreting D♭).
I personally wouldn't interpret D♭ really that way, but instead think of the "flowchart" metaphor again. There's a lot of motion between E♭ and D♭ when they occur. There's a lot of motion between B♭ and A♭. Basically, in a similar fashion to how V/V relates to V in a typical major key, there's an E♭ subsidiary or secondary "tonic-like" area around E♭ in this piece, perhaps. (Again, the E♭-D♭ relationship is like the B♭-A♭ relationship.)
So, you can think of a flowchart that has I and ♭VII, and then there's another part of the diagram that has IV and ♭III, which can also be viewed as having a common relationship like I and ♭VII. These chords constitute most of the harmonic vocabulary of the piece, and you can draw various arrows showing the most common pathways among these chords. For example, sometimes you'll get a direct motion from D♭ to B♭, like in a IV-♭III-I motion (mm. 8-9). Rather than a I-IV-V-I cycle that would appear in a major key piece, this piece appears to use I-♭III-IV-I (as in mm. 5-6). Progressions like this recur later in the piece. They are part of the harmonic "world" of this piece.
Does this fit into a particular "mode" (e.g., Mixolydian)? Not stereotypically, but that's what the piece does. To answer the title question of "how does one analyze a song...", this is the place I'd start, by describing the general content and typical motions of harmony in this piece, particularly the emphasis on IV and the I-♭VII progressions. And you create the flowchart and go from there.
In the end, is it in "B♭ major" or "B♭ Mixolydian" or some other more arcane term for a scale? Not in the most typical sense of those terms, at least in terms of what they imply about harmonic usage. But it certainly uses a type of Mixolydian-like harmony that emphasizes ♭VII in a way I've seen in other pieces. I don't know a specific name for it, but describing the types of motions of harmony here is more interesting (and more like "analysis") than simply trying to put a scale label on it.
EDIT: I just realized that this question has been reworded by edits and originally asked "what key" the piece was in rather than how to "analyze" it. I think I still tried to answer the "what key?" question here, but the bit about analysis may have gone further afield than the original question wanted. Still, to me, the question we should be asking is how to describe the musical features (like harmony, melody, etc.) of a piece, rather than worrying about how to stamp a label on it. So I'll leave my answer as-is.