How do you lose a castle site? A castle is a mass of stonework and mortar.
Many people interested in castles start off by looking at romantic ruins and stately homes, but for me the attraction was a particular castle that had long since disappeared, gone beyond the ruinous, until even archeology might not be able to establish the site.
A lost castle is quite simply a castle of which no discernable trace remains on modern maps, castle lists or at all. Some have skimpy remains, but they lie hidden awaiting rediscovery.
Many of these, such as Robert The Bruce's Manor at  Cardross in Dunbartonshire, Scotland, are physically, but not truly lost. Well documented, through the exchequer as example, and known for centuries as the site of his death, only the location is the real mystery. This is a site of historic importance, but what of the fortified houses of minor local lairds, who never really made it into the annals of mainstream history, replaced in time by a series of more modern structures culminating in a modern farmhouse, or lost in the sprawl of urban expansion.  
An occasional mention may be made in an account of this battle or that event,  of such and such of this place, or simply the place name substituting the persons, indicating ownership or tenancy of the place. Where do we start.
There are various places, one I've mentioned is the occasional mention of a character in an event. This gives a start point for research of that name.
Ploughing through local histories, ancient local descriptions, and old maps by web work or local libraries is par for the course. Searching the dusty tomes of reference sections of far distant libraries looking for snippets of information that helps put the local picture together. A clue here, a fact there, each small collection of information, even a few lines, or discovering which local worthy owned it can be a laborious task. Not terribly exciting for some.
Current maps and a basic knowledge of place name components give clues. Older names contain components of our old languages, and indicate the age of the estate or place as an entity. Following the Agrarian revolution and field enclosure, much later than the castle age, place names tended to be in straightforward English as larger estates wre divided into much more productive tenancies. The more ancient sites have Gaelic or Brittonic components, that often give you a foothold amongst  the myriad of names that can appear on a standard Ordnance Survey map.
Here's a few
 Boreland, West Bore, east Bore etc indicate the site of a home farm of an estate, that which supplied the household,rather than the market. Mains is another, from the latin Manororium, this again described the home farm, but originally was the main house of the manor, as was Cardross.
In the medieval period, the home farm often stood about a mile from the castle, narrowing down the location. English place names too gave clues, castlehill,  for example, but often in central Scotland this describes a Roman site, or just as frequently a motte.
Web searches for archaological remains in the area, help to build the picture. Canmore, the official site of the Royal Commision on Ancient and Historic Monuments in Scotland is by far the best source for this. But it is not exhaustive. It might record a foundation here, or a piece of worked stone there, but it almost always falls short of telling you that it was a castle site. Even in describing mounds, it can be non-commital.  Numerous sources each give you a piece of the jigsaw.
Does this sound boring and an enormous effort time wise for next to nothing?
Information comes in spates and droughts. I once went off to a local library to research one possible site, and within  an hour had 'rediscovered' 16 castles with details of ownership, origins of the estate and even descriptions of some of the buildings. All this from an 18thc local history of an area which by the 20th was buried by several housing estates and a sprawling iron work. I still had no more data on my original target, Bothwellhaugh, and have since discovered that it was a geographical locality, rather than a likely estate, being a small area within a large lordship, Orbistan. There are some great Roman remains there though.
Part of the problem when I started out, was that no-one had really made a definitive list of castle sites. No one has yet or ever will, but I tried on a local basis, Martin Coventry nationaly, and in putting these together he has produced the most comprehensive list of Scottish castles available.
We started essentially from scratch.
The excitement comes in each confirmed site. However insignificant, each had an influence locally, and as you learn about one, you can discover another, as marriages between local families, or minor feuds survive in local memory...or on stone tombstones in ancient graveyards.
Gradually you find yourself unravelling a local story stretching through the centuries and over the miles, until you can drive or walk through the area, and sense the history. You know the story of the land, its people and it's buildings. Eventually everywhere you've studied feels like home.
But the really exciting bit comes when you visit the sites, a crop mark , a pile of rubble or some remarkably well worked stone suddenly draws the attention, and you know you've found the site, or are very close. I spent numerous visits to the hills above Kilsyth searching for any remains of the castle of that name. A lucky bit of research on another site gave me a clue, I moved my search 1/2 a mile away to a local farm and started finding expensively worked stone built into a dyke. This changed my focus a little, and suddenly further web searches and library visits had me trolling through relatively recent archeological reports of an excavation of the foundations of Viscount Kilsyth's castle, burnt and demolished by Cromwell....but only after he'd spent a few comfortable nights in it. For me Kilsyth was a lost site, but someone had got there before me.  
The secret of finding lost sites? Luck, hard work and enthusiasm...in that order.