Avast Ye, Admiral is one of the better known Feats of Strength though it is sometimes called "Bloodsail Buccaneers". One of the nice things about it is that it DOESN'T require you to get all the way to exalted with the faction. The other is that you actually get quite a bit of fun "Role Play" or "Costume" gear out of it. The largest PROBLEM is that it is VERY easy to lose reputation with the faction and this prohibits you from using numerous flight paths which can become troublesome. Now come Cataclysm this hardship will not be as much of an issue.
The only way to GAIN reputation is to kill Booty Bay Faction members but you get the greatest return by killing the Booty Bay Bruisers, all other members will only net you 5 rep each where the Bruisers grant you 25. While you can solo grind, the quickest way to do this is achievement is to get a group together by spamming trade. What I like to do is get a group, inform them to focus on the Bruisers and try to leave the quest givers, Auction house, flight masters and Inn Keepers alone if they want to remain a part of the raid group and get easy rep. I will then announce in General that a raid is going to be farming Bloodsail Rep for the next few hours. While people may not like it I have found it greatly reduces the harsh feelings and general discontent that can happen as a result of this type of thing. Especially if you get some idiots that insist on killing inn keepers, flight masters and quest givers just to be jerks. Remove them from the group and suddenly the rules seem more reasonable when they are no longer able to find any mobs.
By doing this you can obtain the achievement in a matter of hours rather than WEEKS of solo grinding with out all the harsh feelings. Once you reach just over Neutral with the Bloodsail Pretty Boy Duncan will send you to Fleet Master Firallon to pick up a bag full of goodies. This includes a Shirt, Belt, Pants, and Boots. Just a little more grinding will get you to Friendly and the real quest that gives the achievement its name. Avast Ye, Admiral. Now for this you WILL want to announce you are going to be doing the quest because it REQUIRES you to kill quest givers, which annoys lowbies. Kill the Baron and his right hand Tauren and you get yourself a Title and a fancy hat.
Now if you are NOT planning on working on the Insane in the Membrane Achievement and would like to make use of all those convenient Goblin flight paths there IS a way you can quickly get back all that goblin reputation you lost with out losing your new title, though you WILL lose your hard won Bloodsail reputation.
Just outside Bootbay on a nearby hill is the Bloodsail Traitor. He has a quest for you called "Traitor to the Bloodsail" which has you turn in two stacks of Silk cloth and 4 Red dye to deceive the Baron into thinking you have been killing Bloodsail pirates. Another option is to head over to Rachet and speak with Mupsi Shacklefridd, she has a similar quest called "Mending Old Wounds" which only requires two stacks of linen cloth and 4 empty vials. Many prefer this since it is often cheaper and easier to farm. The other options are Rumsen Fizzlebrack in Tanaris with "War at Sea" who wants Mageweave cloth and Strong Flux. As well as Bronn Fitzwrench in Winterspring who is after Runecloth and Coal with "Making Amends". Each of these deal with the specific factions of the zone they are located in. And will take about 168 linen and 336 empty vials, 84 silk and 168 Red Dye, 42 Mageweave and Strong Flux, and 22 Runecloth and 44 Coal to get you back to Neutral with the Steamwheedle Cartel. Or 34 turn ins for each faction if you do them equally. Just check the cost and ease of farming for you then calculate accordingly.
The other option is to head over to Dire Maul North and do Free Knot which grants 350 reputation for ALL of the Steamwheedle Factions EQUALLY without hurting your Bloodsail reputation. I could usually do five clears an hour before I had to sit around and wait due to the "to many instances" debuff. If you focus only on the guards you have a high chance of getting a key almost every run. Take the time to do some full clears and you may also pick up some other goodies like Librams or Pristine Black Diamonds which can be sold to those crazy people going after the Insane in the Membrane achievement.