Do I do as many as possible to failure?
Or do I stick to a weekly plan or multiple sets with low reps?
While there is little disagreement that weight should be added after a certain amount of reps is reached (commonly 15), actually getting there is a different matter. One approach, initially popularized by Pavel Tsatsouline (see this article for more info), is called "greasing the groove". Pavel claims that "specificity + frequent practice = success", meaning, one should train "as often as possible while being as fresh as possible". While this can be interpreted in multiple ways, it boils down to not going to failure on every set and doing several sets daily. Of course, you need to have an easily accessible pull-up bar for this to work.
I've personally followed this approach to work from my 2 pull-ups to ~12 quite fast - I had a bar on my way to the bathroom and my rule was to jump and do a few pull-ups everytime I went under it. Sure, at the start I cheated, jumping more, not going all the way down, but I improved quite fast. Later on, I tried to vary my grip and do them more strictly. Most importantly, I never went completely to failure, just doing however many I could while I felt "strong".
The article I linked to above goes on to mention that this can be applied for other exercises, although it's probably not a good idea (for fear of over-training), though it concludes that doing it with dips might be a good match (which is in-line with my own thoughts and experiences, except I don't have parallel bars handy so I couldn't test it).
Well the best way to increase reps would be to increase absolute strength than cycle back to strength endurance which would carry over to more repetitions.
Example of this method
NFL combine test
One of the tests they have the potential players do is bench press 225 pounds for as many reps as possible to see how much strength they have. So how do those guys manage to do up to 50 repetitions with 225 pounds? First they build absolute strength which is maximum force an athlete can generate. They have to build there one rep maximum so 225 pounds is considered light than 2-3 weeks from the combine test they work on carrying it over to strength endurance which is maximum repetitions.
So to increase reps you need to increase absolute strength on the pull-up.
This article is pretty good. It makes four basic points, including increased frequency, negatives, and assisted pull-ups:
Basically, keep doing them - try different hand positions, add weight and make it a game, such as doing a set prior to every meal and when you wake up or when you pass by the pull up bar (get one in your house on a door frame). There are some basic body weight exercises that you can (and should) do when you can: pull ups, push ups, sit ups......
Do three sets to failure, using some assistance if necessary. Do chin-ups one day, take a day rest, then do pull-ups the next day, and then rest. That should be your cycle.
That may mean your first day looks like this:
That's okay. The next time you do it (4 days later), you may get:
And so on... Your pull-ups will be weaker than your chin-ups, probably.
Eventually, when you get up to 15 reps, you should add weight by hanging plates from a lifting belt and chain.