How were old PvP titles obtained?

There were only a certain number of characters on each faction that could hold each rank. The higher up you got, the less people could hold those ranks. Each week during maintenance the calculations were done and the ranks were updated. Rank 14 (Grand Marshal/High Warlord) was the top rank and would only be given to one or two characters per faction per week.

The person going for the top spot had to climb through each rank, one week at a time, earning proportionately more honor than those below his/her rank. This was also at a time when cross-realm Battlegrounds were not yet available, so it was a major time investment, often required coordination with others on the realm to run specific Battlegrounds at specific times, and sometimes even required cooperation amongst those gunning for rank 14.

Achieving a rank would give players the title while they possessed the rank (for Grand Marshal/High Warlord this was almost always for only a week at a time) and allowed players to purchase the best PvP gear in the game. There were two sets of gear plus some other items that could be purchased. Each set of gear was split in half over two different ranks. So you could buy half of the superior PvP set at rank 8, I believe, and the rest at rank 10. The epic set, I believe, was split between ranks 12 and 13.

When we did away with that Honor system at the beginning of The Burning Crusade, we allowed players to wear the highest title they had achieved over their head. That is how the titles currently exist today.

Q u o t e:
Not quite.

You only advanced if you played more than X other people at your rank. And you lost honor every week unless you kept playing. Sometimes you even lost honor even if you did keep playing. Honor decay sucked.

Ah yes, and there was Honor decay. One had to essentially outdo oneself each week just to make any progress.

Edit: A bit more information on these titles can be found here: http://www.worldofwarcraft.com/pvp/ranks.html