I was looking at this program and it seems that deadlifting only 1 set of 5 repetitions each working day is too little to achieve the goal of adding weight each time.
Or have I misunderstood it?
The reason you only do 1x5 with deadlifts is because you already are doing 5x5 squats, making the deadlift an almost redundant exercise. As Mehdi says, since they target a lot of the same areas, by the time you get to your deadlifts you will be GLAD that you only have 1x5 to do.
At the beginning when the weights are very light, you will certainly feel like you can do more. Personally, I choose to do 5x5 deadlifts in the beginning when the weights were light; I knew I could handle it and it helped me practice my form. However as the program progresses, you will find that your body simply cannot maintain 5x5 deadlifts and won't recover fast enough.
As to the point of adding weight, it's not really that difficult. Unlike the overhead press or the barbell rows, the deadlift is a full body compound exercise and as a result you can go much further before hitting a plateau with the deadlift. Also, even though you only deadlift 1x5 every other workout, you are still building the necessary strength from your other exercises.
Deadlifts are only 1x5 because you should be moving a vastly heavier weight with them than with anything else. The deadlift is the most efficient of the lifts and allows the most load. That's great, except that doing sets across is generally not necessary with a novice's sets of five, and doing additional sets with any real weight makes for a brutal recovery, as well as a higher possibility of injury due to improper form from fatigue.
Everyone I know who does StrongLifts, Starting Strength, or other 5x5/3x5 programs has no problem adding weight with deadlifts at 1x5 for quite a long time. I'm zeroing in on a double bodyweight deadlift with only one work set.