How do people get into lost media searching?

well theres no one specific way to start searching for lost media, a lot of times people find lost media on a wim or by mistake. Usually if you wanna start a search get people interested in what your looking for, find any surviving info about it (Who made it, what company disbuted it, any surviving copies known to exists) and go from there, contact people known to have been associated with it, search the internet, might be hiding under a different name. 
For well known topics, look at what is already known and go from there, what leads sounds most convincing? Look at the known info and create a new lead not thought of yet. These are just some ideas though, there is no specific way to search, for all you know it could just be hiding under your nose the entire time

this should go into off-topic but i guess like learning that it exists

easy, just collect tv shows/cartoons/movies

and you'll find that either for shows (especially in the old days)
that episodes would be missing, for American aired shows,
the ones that would usually be missing were the seasonal episodes,
such as the Halloween and Christmas ones.

because the USA only airs (or used to air) those during said times.
i remember this especially being a thing with people who would record
cartoons from TV.

sometimes certain episodes were/are never or barely even aired
(such as The Robonic Stooges - Dimwits and Dinosaurs)

other times you try collecting a show, and it hasn't been aired
since the original run or time period it was actually released.
for example, The Harlem Globetrotters, hasn't been re-aired since about 2004.
and is not on dvd/streaming/blu-ray either.

you could even be dealing with banned episodes
(such as Cow and Chicken - Buffalo Gals)

which although available now, was at one point completely lost.
same for Cow and Chicken's Pilot episode "No Smoking"
which i helped with to finally get it online (this was around 2008)

sometimes there's shows (which happens a lot on this forum)
where the original airing is different from later re-runs/dvd/blu-ray
so people try to find the original airings.
just to name a few such shows:
Family Matters / Scrubs / That '70s Show / My Name is Earl / Married with Children

as for movies, same thing.
TV airing being different from dvd/blu-ray/streaming
missing or deleted scenes / replaced music / etc.

it's very easy to stumble onto stuff that is lost,
at least in my case for TV shows.
i don't mess around with collecting movies.