There are loads of fan-theories as to how they would know specifically; my favorite is, based on how confidently Dumbledore explains exactly what happened that night, that he used Legilimency on the newly orphaned Harry. Another fairly prevalent one is that the scar Harry has is unique for being the result of a Killing Curse, yes, but curse scars in general are not unique at all. They also could have used any number of detection spells--honestly, there are a multitude of options.
What I thought was wrong was that McGonagall explicitly said that the Killing Curse struck directly at the soul, severing it from the body. This is why victims of Avada Kedavra don't have a mark on them. But Voldemort's body was a "burnt hulk." Odd, that...
At this point in the story Harry has never even heard of Avada Kedavra, never mind what someone who's been AKed would look like.
[EDITED to add: The relevant question isn't whether there are in the Potterverse or the Methodsverse ways in which wizards might be able to know what happened that night despite there being no survivors other than the infant Harry, but what rational!Harry could reasonably have thought possible and plausible.]
Update: Discussion has moved on to a new thread.
The load more comments links are getting annoying (at least if you're not logged in), so it's time for a new Harry Potter and the Methods of Rationality discussion thread. We're also approaching the traditional 500-comment mark, but I think that hidden comments provide more appropriate joints to carve these threads at. So as of chapter 67, this is the place to share your thoughts about Eliezer Yudkowsky's Harry Potter fanfic.
The first 5 discussion threads are on the main page under the harry_potter tag. Threads 6 and on (including this one) are in the discussion section using its separate tag system. Also: one, two, three, four, five, six. The fanfiction.net author page is the central author-controlled HPMOR clearinghouse with links to the RSS feed, pdf version, TV Tropes pages, fan art, and more, and AdeleneDawner has kept an archive of Author's Notes.
As a reminder, it's often useful to start your comment by indicating which chapter you are commenting on.
Spoiler Warning: this thread is full of spoilers. With few exceptions, spoilers for MOR and canon are fair game to post, without warning or rot13. More specifically: