Well, at one level, it is a very intuitive matter. We have to 1.) know that the piece in question did at one point exist, and 2.) NOT know where to find any surviving copy of it.

The ways we can know point 1 are varied, and may range from catalogues that the composer themselves maintained, letters mentioning said works, ancillary material such as opera libretti or programs attesting to a work's existence, etc. There are complicating factors though. Perhaps our only sources are not 100% reliable. Especially if our only evidence of a composition existing is second or third-hand knowledge, a historical witness may just simply be wrong and the composition never existed. Furthermore, letters or other primary sources may refer to works obliquely or vaguely, which may cause confusion or conflicts among historians.

Now, number 2 is a bit trickier, because we may "lose" a work at any time and in any number of ways. Theaters, libraries, museums and churches can burn down, be looted, or destroyed in global conflicts, for instance, or private collections auctioned off and the recipients lost. I can think of several times when I find a manuscript listed in some 19th century catalogue of some random Italian library floating around on Google books, only to discover that said library no longer exists. Then there are other libraries that simply don't have great record keeping. I hear terrible things about the Luigi Cherubini conservatory in Florence, for instance. Who even knows what's in those libraries!

But all of this is a matter of who is doing the cataloging, for what purpose, and how thorough they are being. For people that we really care about in music history, your Mozarts, your Bachs, your Beethovens, etc., tons of people have poured a ton of work into tracking down every lead they can. If there's a lost Mozart work, you can be pretty sure that at least a few people have tried very hard to find it, and while that doesn't mean it doesn't exist in some vault somewhere, it does mean that the chances of it being found are probably pretty slim (though it does still happen).

On the other hand, I am probably the only person on planet earth who cares about Angelo Tarchi's 1790 setting of the opera L'Olimpiade, an opera that we know existed, and which the New Grove dictionary says it held at the Bibliothèque Nationale de France, but when I search through their catalogue, I get nothing. As a poor grad student living in the USA, for all intents and purposes, I consider that to be a lost work. I likewise consider this manuscript auctioned off by Sotheby's to be lost, as I have tried repeatedly to get in contact with whoever they sold it to, and no body returns my emails. So this is a manuscript that clearly exists--somewhere--and there are likely records at Sotheby's detailing where it is. But as I can't access those, the works contained in this are, again, from a practical standpoint, lost (I mean, really, there's no guarantee that some billionaire didn't purchase this manuscript to use as toilet paper! I have to hope that isn't the case, but the fact is that I cannot ascertain the current status of this document). Each of these things are likely problems that have solutions, but solving them requires having friends in the right places, or having the right resources. The perceived importance of what you study partially determines the amount of resources you are able to spend to investigate a matter, and that, in turn, will place practical limits on what you can do to "find" lost works.