how did we figure out they were there, and which PIE words had them and which ones didn’t?

Mostly by the effect in the nearby vowels - often, a sound triggers changes in nearby sounds, before being dropped.

Here’s an example. Greek often shows an initial vowel where other IE languages show none. Like this:

Greek	Sanskrit	Latin
ἐλεύθερος / eleútheros “free”	–	līber “free”
Ἔρεβος / Érebos “Darkness”	रजस् / rájas “darkness”	–
ἀστήρ / astḗr “star”	स्तृ / stṛ́	stel[la] “star”
ὀδούς / odoús “tooth”	दत् / dát “tooth”	dens “tooth”
ᾰ̓γρός / ăgrós, “field”	अज्र / ájra “field”	ager “field”

Disregard for a moment the last line, focus on the first four. Why is Greek showing “random” initial vowels where Sanskrit and Latin have none? There’s no underlying pattern; it’s probably inherited then.

However, you can’t simply claim that Greek inherited the vowel and the other two lost it, without causing a problem: why didn’t Sanskrit and Latin delete the initial vowel from अज्र / ájra and ager?

The solution that a linguist called Saussure found to oddities like this was to propose that PIE had three sounds, not directly inherited by the descendants. He called them *ə₁ ə₂ ə₃; nowadays we call them *h₁ h₂ h₃. In that specific environment (word start, before a consonant):

• Greek: h₁→e, h₂→a, h₃→o.
• Latin, Sanskrit: get rid of them

And the initial vowel in the fifth line (that pops up in all four) is actually inherited.

(The ancestors of those five words are nowadays reconstructed as *h₁lewdʰ-, *h₁régʷos, *h₂stḗr, *h₃dónts, *h₂éǵros. Sure, the fifth one has a laryngeal… but also a vowel, that’s the vowel being inherited by Sanskrit and Latin.)

That hypothesis also helps in quite a few other situations, like:

• Why do sometimes a long vowel pops up from nowhere? A: short vowel + laryngeal.
• If PIE loved triconsonantal roots so bloody much, why do some roots have less consonants than expected? A: a laryngeal got deleted.
• Where did Sanskrit get those aspirated consonants from? A: from a stop consonant followed by a laryngeal.

Also, note that, when Hittite was discovered, all that “laryngeals” talk stopped being just a conjecture - because Hittite did preserve at least *h₂ and *h₃, and probably also *h₁ (it depends on how you analyse the cuneiform spelling).

PIE might not actually even exist, there is no proof of it. The hypothesis is that there used to be only one language in the Indo-Europes 4500-2500 BCE, And and as speakers were mose isolated, regional dialects began to form, and thousands of years later they became distinct languages. But we don’t know anything about PIE itself. It’s a mess.

Anyways, as for your question: they noticed things off about some words, and it was theorized that there were other letters. These are the Laryngeals.