(abridged). We outline LBCS (the LOFAR Long-Baseline Calibrator Survey), whose aim is to identify sources suitable for calibrating the highest-resolution observations made with the International LOFAR Telescope, which include baselines >1000 km. Suitable sources must contain significant correlated flux density (50-100mJy) at frequencies around 110--190~MHz on scales of a few hundred mas. At least for the 200--300-km international baselines, we find around 1 suitable calibrator source per square degree over a large part of the northern sky, in agreement with previous work. This should allow a randomly selected target to be successfully phase calibrated on the international baselines in over 50% of cases. Products of the survey include calibrator source lists and fringe-rate and delay maps of wide areas -- typically a few degrees -- around each source. The density of sources with significant correlated flux declines noticeably with baseline length over the range 200--600~km, with good calibrators on the longest baselines appearing only at the rate of 0.5 per square degree. Coherence times decrease from 1--3 minutes on 200-km baselines to about 1 minute on 600-km baselines, suggesting that ionospheric phase variations contain components with scales of a few hundred kilometres. The longest median coherence time, at just over 3 minutes, is seen on the DE609 baseline, which at 227km is close to being the shortest. We see median coherence times of between 80 and 110 seconds on the four longest baselines (580--600~km), and about 2 minutes for the other baselines. The success of phase transfer from calibrator to target is shown to be influenced by distance, in a manner that suggests a coherence patch at 150-MHz of the order of 1 degree.