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:
The reason people are unable to do more pull ups and chin ups is because their body weight is too heavy for them. If this was the problem with any other exercise, you could just take some weight off the bar or use lighter dumbbells. Unfortunately, you can’t take off your legs to lighten your own body weight. However, there are ways of creating the same effect.
Assisted Pull Up Machine. This is probably the easiest way to do it assuming your gym actually has one of these. If so, what this machine basically does is it takes away a portion of your body’s weight by balancing it out with weight from the machine (like how a see-saw works). You set how much of your weight you want to pull, and it provides the counter weight to balance it off. Your goal here would be to gradually increase the amount of your own weight your are using until you get to the point where you can pull 100% of your own weight. At that point, you can do actual pull ups. Bands. You know those elastic workout bands that people use for 100 different things? Well, if you hook the top of the band around the pull up bar, and then rest your knees in the bottom part, you create what is called a band-assisted pull up. Get A Spotter. Similar to the band method mentioned above, you could just as easily have a friend supply the “assistance” by putting their hands under your feet/ankles/knees.
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.