For this particular tune, there are three approaches that will definitely work. I'll give them to you, easy to hard.
I'm assuming you're using the actual album transcription. It's for Trumpet, Alto, Tenor and Bari and Rhythm section which is what they use on the album "The Blues and the Abstract Truth." (Get this album if you don't have it already.)
As I mentioned there are three tried and true approaches that will work with this tune. The following link contains a pdf with examples of these concepts on a two staff score. I'm using the 1st two bars of the head for this example. https://dl.dropboxusercontent.com/u/58030009/Stolen%20Moments%20Suggestions%20for%205th%20horn.pdf
EXAMPLE 1: The simplest and easiest way to add a 5th horn to this is to simply double the melody - at the octave or down an octave. You can just do this in the trombone, open - or in a mute for a little extra color. If I were using this approach I might put the melody in the tenor part and give the tenor part to the trombone (and the practice transposing the part is good for you). Do whatever you like - just remember, when doubling parts, it's usually not a good idea to double a harmony part without also doubling the melody, so if you're adding a 5th part to a chart that has 4 parts, don't just double the 3rd part. If you do that, a part that's not the melody will be the loudest part. We don't want that.
EXAMPLE 2: The cool thing about this tune is the fact that the bass is playing a specific ostinato and not improvising a walking line. Because of this, the bass is functioning as it's own counterline. You can double this part. If your trombonist is a bass trombone player, it would be good to try this. If not, you can double the bass part in the bari and give the original bari part to the trombone.
Example 3: Okay, caveat about this approach - complex does not always mean better (rookie mistake) and this is the most complex approach of the three, adding a separate 5th part by adding color tones. I'm kind of using a Bill Evans approach here, adding tones a 4th below the lowest pitch in a way that sort of mimics his voicings on Miles Davis's "So What". In many (but not all cases) the results in a color tone (9/2, 11/4 or 13/6) being added to the chord. In the 2nd bar on beat one I'm violating a rule called the "flat 9 rule" but because of the voice leading it works - and that note doesn't last long enough for the dissonance to register. As the chord gets lower I get away from voicing the color tones so low to avoid a muddy sound. Learn all 4 parts on piano, and work on adding your own notes to thicken the chord if you want to try this approach.
I don't recommend adding countermelodies and long tones to a tune like this. This tune produces a specific vibe, and this arrangement is classic. Keep it in the spirit of Nelson's original intent by sticking to one of these three approaches. There are two lines to this - the harmonized melody part (also called a "thickened line" and the bass ostinato. Adding a separate countermelody or longtones to this tune isn't really necessary and would be stylistically incorrect in this case.
Also, JJ Johnson does this with a big band on his album "J.J.! (The Dynamic Sound of J J Johnson with Big Band." - It's track 2 right after El Camino Real. He does it in D minor, not the normal key of C minor. Great arrangement, and a great solo to learn. You can also find this same track on a compilation titled "Say When."