Lots of good tools exist that help in locating underground utilities. In some cases a transmitter is placed on a line, conduit or other conductor. A fairly sensitive reciever is used to pinpoint the location. Many of the devices are about 1 meter long with a handle readout on one end and the sensor that is close to the ground at the other end - so the user can walk along and find the item of interest. Some work as Nigel suggests on the magnetic field - others look for a specific signal. Ground penetrating radar is used for larger surveys.
In many areas here in US it's mandatory to have what's called a "stake-out" done before digging. Crews from various utility companies show up with all sorts of locators. Each one locates their item quickly with the portable tools then spray paints on the walk, grass ,whatever.
One other possibility is that there might have been clues that you just don't recognize - a bump in the wall, a conduit or meter inside.