How do "we"/they actually know Voldemort even used the Killing Curse that night, as opposed to doing some other thing? ie, how is it known that he is the Boy Who Survived the Killing Curse in the first place?

That's a good point... though if I recall, he is just known as The-Boy-Who-Lived. In canon, it's not revealed until book 4 that he is the only one to have ever survived the killing curse, in particular, and it's Znq-Rlr Zbbql who says this (though, in truth, it was Onegl Pebhpu We.). Onegl Pebhpu is a highly loyal Death Eater who had been in contact with Lord Voldemort, so maybe the dark lord just told him? Though it's probably more likely that everyone just assumed Voldemort had used his favorite curse.

What bugs me is how they know that Harry is the first and only person to have ever survived that curse. I mean surely, sometime in the entire history of wizards and witches, somebody has sacrificed themself for a loved one who was then Abracadabra'd (i.e. did just what Lily did). /shrug

edit: Redacted a name.