A root-and-branch inquiry: Inside the deep-digging, money-spinning, web-crawling world of family trees

Thanks to the internet, we have become a nation of amateur genealogists: last year, 20 million of us went online to learn more about our family trees. And it's an addictive habit. Just ask David Randall, who began researching his clan a few months ago — now he thinks he may be close to solving the mystery of his great-uncle Sidney...

When you're gone, you're gone, eh? You'll have had your fun, or been released from your misery, and heading toward the last of the real seven ages of man and woman; baby, grown-up, parent, grandparent, great-grandparent, grandparent's grandparent, and, finally – when there's no one alive who can remember you even existed – anonymity and nothingness. There might be some trace of your dust in the cemetery, but, save for keeping some little corner of our species going, you might as well not have been here at all.

Except for one thing: you will have been given a chance for a sort of immortality. In death you will have been turned into one of a number of compulsorily preserved records. And, some day, if one of your descendants is gripped by the desire to trace their ancestors, they will find you, and, in our secular age's version of resurrection, rescue you from oblivion and give you a new existence as part of their family tree. And while you wait for discovery, you will reside in the one place we are all certain to go when we die: to sit, in databased limbo, as census records of what, and where, you once were. This is our society's Valhalla, housed in a sprawling building in Kew, west London.

Astonishing numbers use these records. Twenty years ago, when tracing your family tree was, for non-aristocrats, something of an eccentric hobby, a fraction of us made the pilgrimage. Last year, according to findmypast.co.uk, nearly a third of the population made some inquiry about their family's history. The transforming power of the internet was at work, and, in 2009, more than 22 million visits were logged to the National Archives website, quadruple the number of just four years before. Businesses that help you track your ancestors online are in the midst of similar booms. Ancestry.com's global network of websites has more than a million subscribers, who have built more than 12 million family trees; visits to thegenealogist.co.uk have doubled in the past three years, and Genes Reunited has – despite a habit of offering connections to people no more likely to be your relations than a Himalayan yak-herder – 10 million members, five times what it had in 2005.

There are now some half-a-dozen magazines on the subject, and, each month, 130,000 people buy one of them. Their advertisements are a tribute to an industry (for that is what it now is) that is almost indecently thriving. On offer are software programmes which let you build a permanent, searchable record of great-uncle Freds and distant cousin Annies; family-tree charts (for those who wish to enliven social occasions by whipping out a sheet showing the complete antecedents of the Froggats); photograph restorers (great-aunt Eliza in full flush again); Latin translators (go back far enough and you will need it to read church records); books (Tracing Your Criminal Ancestors is popular, at £12.99); CDs of archives (Shropshire Quarter Sessions Abstracts 1660-1889, a snip at £14); events (Bracknell Family History Fair at the local sports centre); hopeful classifieds (Colin Jelley, for instance, is interested to hear of any other Jelleys); and pages and pages of small ads for county-records researchers, some of whom have adopted jolly names such as Anzestry, Branchlines, or, for the wince-proof with Scottish connections, My Ain Folk. All this plus, for those who can't reliably add or subtract, the BMD Wheel for instantly calculating dates and ages, at £3.81 plus p&p.

If none of that satisfies your curiosity, there is always DNA testing, to establish the deeper, racial mixture of which we all consist. It has its critics, who point out that you can pay hundreds of pounds merely to be told your ancestors were "of either Arab or Irish descent", which suggests a certain imprecision. And, for the really big genealogical splurge, there are firms such as Ancestral Footsteps, which offers chauffeur-driven, luxury-hotelled, five-day tours of your antecedents, all in the company of your very own personal genealogist, who will have conducted what the company promises will be "months" of research aided by "specialist fixers". The cost? A mere £20,000 – or £7,000 for the cheapskate's weekend version.

What has probably done more to boost the popularity of family-tree tracing than almost anything else is the BBC programme Who Do You Think You Are?. The show, which began in 2004, reveals the roots of well-known people, ostensibly showing them quarrying away at the historical coalface, but, in reality, following the route pre-set by diligent backroom genealogists. It has spawned the inevitable BBC magazine, a DVD (containing a seriously aggravating number of shots of celebs staring wistfully out of train windows or driving down country lanes), and an exhibition, at Olympia no less. This year's runs from Friday to Sunday, and will have no fewer than 200 exhibitors. Some 15,000-plus are expected to visit, and they will, if they take up the pursuit, discover not only their ancestors, but also something they perhaps did not expect to find: that searching for your roots is seriously addictive. They will become genealogy junkies. I should know. I've become one of them. Worse, I'm a recent convert, a missionary, a walking, incessantly talking advocate of family tree-building.

It was something I'd said I would do "one day", and for me, that time arrived when the last of my parents' generation died, and there was no longer a brain to pick about my family of long ago – not just their jobs, marriages and war service, but the things you can't get out of a census or death certificate: their character.

I had an aunt – my only one – who lived with every faculty but the one to sprint until the age of 96. While she was alive, I kept thinking I should invite myself over and quiz her, but could never quite bring myself to do it. It seemed to me that doing so might alarm her, and look as if I had been made privy to some gloomy medical news, and that she was, although she didn't know it, set for imminent departure. She died in November, and, save for a booklet of memories she wrote for my cousin's daughters, her memories died with her, as do those of so many.

Visiting my daughter-in-law's parents at Christmas, I was shown two paintings of their East India Company ancestors, and a family tree that included the poet William Cowper. Thus inspired, I made a few tentative online inquiries. Within a day I was a member of ancestry.co.uk, and spending hours online each day, pecking away at history. It is a sickness, I suppose, but those of us who've gone down with it feel only benefit.

I have learnt things; among them, just how distorting is Who Do You Think You Are?. The programmes always – suspiciously always – have some "revelation" (Jeremy Clarkson's ancestor who invented the airtight Kilner jar, for instance, or John Prescott's incestuous great-great-great-grandfather, who, by fathering children with his daughter, managed the trick of also being his great-great-grandfather). The result is the misleading impression that all of us have some entertainingly novel forebear, harbouring wealth, fame, or dark secrets. Sir Michael Parkinson's family was reportedly judged to be too mundane to be one of the programme's subjects, and I know how he feels. My great genealogical discovery is that I am – according to the authority of official records – the latest in a long line of uninteresting people. I have scoured back to 1680, and there are, to my great disappointment, among all the 516 people populating my tree, no pox-ridden whores, horse thieves, embezzlers, bigamists, workhouse inmates, trick cyclists, nobs, slobs or yobs. Just people who were born, learnt a trade, married, had children, and died. My lot (and my personal recollections reach back to the generation born in the 1880s) are relentlessly, pathologically, incorruptibly normal.

Except, perhaps, for great-uncle Sidney. Every family has its little mysteries, and he is one of mine. In fact, his whole branch is rather shadowy, for reasons which require a little wander down Randall family by-ways to explain. My mother was a Plaice (it helps to have unusual surnames in your past – heaven helps the Smiths and Jones), and she had what might be described as a troubled relationship with her father, one Percy Plaice, born in King's Lynn, Norfolk. He was a compositor, a dab hand at drawing, and used the early years of his retirement to travel the world. My twin brother and I adored him. (A sample of recollected conversation when we were very young: "Grandad, what colour are stomach aches?" Grandad: "Blue." And, to prove the point, he drew us one.) Yet we saw too little of him, partly because of his travels, but mainly because, unbeknown to our tender minds, he was, with good looks which lasted well into late age, something of a ladies' man. The story goes that the older wife who bore my mother, plus five sons (all of whom died before 17), once had to visit his place of work to confront him and his current inamorata. His wife died in 1953, he later married his office lady friend, and relations between him and my mother were broken off for some considerable time. He died when we were teenagers; we were told it was "not necessary" for us to be at his funeral, and my mother, despite frequent probings by my twin and me, would never talk of him.

He had an older brother called Sidney, of whom I could find no trace after the record of him as a child of seven in the 1891 census. Then, in a sure sign that I was now hopelessly hooked, I joined findmypast.co.uk, because it had the 1911 census, and I thought I might catch a brief, pre-war glimpse of him. But there was no sign of him there either. Then, a few night's further gropings later, I found him. There, in a record of those sailing off to the colonies in the very late 1930s, he was. At the age of 55, Sidney had emigrated to Adelaide, sailing first class on the steam ship Themistocles of the Shaw Savill line. Did he make his fortune here and go to Australia to spend it? Or, given that October 1939 was his date of departure, was he one of those monied folk who, at the outbreak of war, went off in a funk to where no bombs would fall?

Well, these things are possible, but the purser's careful lettering on the ship's passenger list suggests another reason. Besides Sidney's name, in the column headed "occupation", is the word "retarded". There is really no mistaking it, for "retired" or any other word; and one is left with the terrible thought that poor old Sidney was bundled off to the other side of the world to see out his days in sunny mumbling. Or was he, perhaps, a shell-shocked veteran of the Western Front, who, a family council had decided, should be spared the coming Blitz and sent to the care of an emigrated Plaice? Until the records of the state of South Australia have been prised open (and they sound notoriously clam-like, according to what Ancestry's expert Dan Jones tells me), we won't know. And that, I suspect, however routine your family at first seems, is what keeps people worrying away at their ancestors for years: there are so many loose ends.

Some can be cleared up. My wife's mother was, to the shame that bothered her to the end of her days, born out of wedlock. No big deal today, but a considerable stain in rural Berkshire of the 1930s. Her father later married what would be her stepmother, a not entirely wholesome woman responsible, I suspect, for putting her into service at the age of 13. She had the nervous manners of a novice under-house parlourmaid all her days, yet what troubled her most was her illegitimacy, and the stories she was told of her mother's affection for a variety of GIs. It is one of life's pricking ironies that, when I went in pursuit of these matters on ancestry.co.uk, it took me a mere evening to pin them down. She was indeed born out of wedlock, but her father married her mother within 18 months, and this poor woman died at the age of 32, fully a year before any GIs arrived. If only I'd found these things out before my wife's mother died.

Other people's myths can take longer to prick. As a child, Gina Dawson of Suffolk was told her father was a US airman called David Conley. Then, at 21, she discovered it was actually another from the same airbase, a Constadinos Pappas. She made hundreds of phone calls to try to track him down, and even hired a private detective. It was only when she joined ancestry.co.uk, and used its ship's passenger lists to find her father's original 1920s emigration to the US that she found a relative, his sister, who told her he was a wealthy diamond dealer, but unfortunately a late one, having been killed by a swarm of hornets in the 1960s. Then there's Linda Hutton, from Barnsley, who spent 15 years researching her tree but just could not decipher the true story behind her husband's great-grandmother. It turned out, after much quarrying online and off, that the crafty old girl and her mother had both lied on their marriage certificates, the latter claiming to be a widow to disguise the illegitimacy of a child.

I lack the patience of a Gina or Linda. Within hours of joining ancestry.co.uk, and having full access to hundreds of years of records, I had rushed back through four centuries on the direct male line, to a man who left Hertfordshire in 1635 to become one of the earliest settlers in Massachusetts. I even found his father, born in the late 16th century. "Great-great-great-great-great-great-great-grandfather was practically one of the Founding Fathers," I told my wife. The preening did not last long. What I had done, in pursuing ' the antecedents of an Elizabeth Wright, was assume that the same name meant the same person. Silly. A check the following morning told me that my Elizabeth Wright was not the Massachusetts man's Elizabeth Wright. I reluctantly accepted that I had to do this research systematically, double-checking dates, names and connections, and getting to grips with census, birth, death and marriage records, and their not inconsiderable foibles.

While censuses are pretty complete (gaps, such as Belgravia and Woolwich in 1861, are rare), what you are searching is a transcription of them. This introduces a Chinese whispers element. Before 1911, the census was done by giving householders a form, which they completed in their own hand. Enumerators then filled out a return based on the householder's writing. What you are therefore searching is a third person's reading of the enumerator's hand-written interpretation of your relative's scrawl. Thus, I have found my surname rendered as Randall, Randle, Randell, Randale, and even Randoll. (The trick, according to experienced researcher Dave Annal, is to use an asterisk when searching. This stands for any missing characters. So, in the example he gave in one of the excellent National Archive podcasts, if your name is Shepherd, which can be spelled a multiplicity of ways, then type SHEP*RD, thus capturing all variants. His other great tip: with census records, search for the person in the family with the most unusual Christian name – a trawl for a Hypathia Smith more likely to be fruitful than one for her mother Jane.)

In my researches, I had two great pieces of luck. The first was a large, black, leather-bound family Bible, bought in the mid-19th century, and its flyleaves filled with the details of my great-great-grandfather Frederick and his family. It tells the date of his marriage to Eliza (20 April 1829), and the dates and even times of the births of all his nine children, five of whom survived. Thus, to take one sad little example: "James Randall, born October 31 at 10am 1836, died November 29th 1838" – the day after his new brother George was born. The other great good fortune was that the Randalls were, until mid-20th century migration to the outer suburbs, a London tribe, and few places have better records than the capital.

The place to explore them is the London Metropolitan Archive, whose huge holding of records are now being put online at ancestry.co.uk. London parish records of baptisms and marriages going back to the 1500s are already available, and in the pipeline are wills, school rolls, electoral registers and the paperwork accumulated by the capital's poor-law guardians. I was shown the latter, bound in leather volumes as thick as a footballer's thigh, being digitised. Eight people sat at large desks, clear plastic sheets were pressed down on the open volumes, and photographs taken. (Transcription, so we can all search for our own little Oliver Twists, might follow; a huge task which, for some records, is sometimes aided by Ancestry's 33,000 volunteers around the world. Microfiches, the staple of county-records offices and the nearest old-time genealogists got to new technology, are sent off to the US, where magical machines digitise them.)

Records from the likes of workhouses and the armed services can, Ancestry's head of content Dan Jones explained to me, give surprising amounts of detail of someone's height, appearance and even character. (A future Ancestry project, for instance, is capturing the archives of old railway companies, which often include disciplinary reports on staff.) And such fleshing out of the bureaucratic bones, it seems to me, is the great missing element in basic family-tree building.

Follow your line back to 1453, if you can, but it won't have real life unless you do more than collect mere dates, places and occupations. Anecdotes, and personal recollections are not normally a problem for the past two or three generations. My father's father (born 1881) died in 1940 during an air raid, but anecdotes about him abounded when I was young. He was a tireless practical joker, and the founder of extravagant family Christmas celebrations that meant starting building the scenery for the front-parlour show in November, rehearsing it in December, and, just before the 25th, even stenciling programmes, which came complete with facetious announcements based on the past year's family happenings.

But what of the early generations, those whose habits, pastimes and natures went unrecorded? Well, some contextual flesh can still be put on the bureaucratic bones of their lives. Take my great-great-grandfather Frederick, a Wiltshire bastard who took his mother's surname, came to London, worked as a shoemaker, married, and raised a family. He lived, for nearly 30 years in the mid-19th century, in two Westminster streets which disappeared in the expansion of Whitehall in the 1870s: Charles Street and Gardener's Lane, both a block south of Downing Street. This makes his address sound grand, but census returns tell another story. A look at Charles Street residents in 1841 shows that it was a road of multi-occupied houses (typically two or three families each), filled with 732 members of the tradesman class, fully half of whom were under 25. They included: 11 policemen, nine tailors, five bakers, four engravers, three booksellers, and one each of a large range of useful folk, including a valet, schoolmaster, stay-maker, plasterer, jeweler, typographer, goldspinner and surgeon. From oldbaileyonline.org, a wonderful repository of trials from 1674-1913, I know that the pub two doors down from Fred was the Essex Serpent, kept by Mary Nurse, a widow; and that many locals ate at Mr Rutt's coffee-house. And, thanks to an 1862 map, I know Charles Street was so close to St James's Park that Fred's children would have been able to use it as their back garden. There is so much left to explore: school and trade records, poor-law books (was he, for instance, ever asked to support his old mother and feckless father back in Wiltshire?), Chartist archives (his Westminster home and artisan calling make it likely he was involved), and those tantalising connections hinted at on marriage records. Who, for instance, witnessing Fred's wedding to Eliza at Lambeth in April 1829, was Thomas Garlick? His best man? His adoptive father? Or just some passing stranger?

I'll keep plugging away at these things, and, in time, rescue Fred and his kind from obscurity, and give them the minor immortality of a branch on my tree. It seems – given that they, however distantly, gave me life – the very least I can do.

For more on the exhibition: whodoyouthinkyouarelive.co.uk

Research tips

If you lack a married woman's maiden name, scan census returns for visitors staying with the family. Mothers-in-law are often among them, and their surname will, of course, be the wife's

Names are often misspelt on census returns. Using an asterisk when searching, which stands for any likely wrong characters, will allow you to capture all possible variations. Thus, "Robs*" will get Robson, Robsen, Robsin...

When searching sites such as Ancestry, always use the "exact match" search – or receive an intimidating number of results

Ages on censuses are not to be taken as gospel. In the 1841 census, enumerators rounded down ages over 15, so someone of 28 was recorded as 25. Some of your ancestors may not have known their precise age. And some might have had reason to lie

Occupations can reveal false trails, especially with people of common surnames. William Jones, Westminster labourer married to Eliza Wilson in 1851, for example, is unlikely to have become William Jones, Westminster barrister married to Eliza Wilson in 1871. DR

Roots manoeuvre: Three celebrities who got more than they bargained for on the BBC's 'Who Do You Think You Are?'

Jeremy Paxman

The Newsnight hard man was left humbled by the prejudice and poverty his forebears had to endure. In particular, at the close of the 19th century, Mary, his great-great-grandmother suffered the loss of her husband, the denial of any part of his military pension to support her nine children, and years in a Glasgow tenement, without any poor relief. She eventually emigrated to Canada.

Carol Vorderman

Vorderman knew little about the experiences of her father Tony during the war, beyond a claim that he had been part of the Dutch Resistance. A TV appeal for information led to a meeting with a friend who had hidden Tony from the Germans. More digging revealed his connections with a hotel known as a centre for illegal pamphleteering. Most dramatically, a 1944 police report detailed a failed escape attempt: in crossing a river with 12 others, Tony injured himself setting off a land mine. Only one of the party escaped to freedom.

Ainsley Harriott

Harriott's roots lie in the British West Indies; his great-grandfather served with distinction in the colonial West India Regiment. Harriott knew slavery loomed large in his heritage, but not in the sense he had thought: his great-great-grandfather James Gordon Harriott had not been a slave, as family lore had it, but the descendant of white slave owners. Further detection work uncovered another relative who, during the era of slavery, was notable for being an unmarried "free black" woman whose wealth enabled her to own seven houses. Miranda Porter