What we know from Dune Messiah:
The woman killed was Lichna, the daughter of Otheym. Scytale murders
her to assume her identity to get close to Paul. The reader knows
this, but the characters in the story do not.
So first off, we know that genetic identification is impossible.
"We may never learn who it was died here," he said. "The head, the
teeth are gone. The hands... Unlikely such a one had a genetic
record somewhere to which her cells could be matched."
Also what she was wearing at the time of her murder wasn't particularly Fremen. She was not wearing a stillsuit, but a blue robe:
"We have the woman here," Farok said. "Do you wish to see her now?"
"I've seen her," Scytale said. "I've studied her with care. Where is
Farok snapped his fingers.
The youth took up his rebec, drew the
bow across it. Semuta music wailed from the strings. As though drawn
by the sound, a young woman in a blue robe emerged from a doorway
behind the musician. Narcotic dullness filled her eyes which were the
total blue of the Ibad. She was a Fremen, addicted to the spice, and
now caught by an offworld vice.
So with most of the major features missing (dental/cranial), and no genetic record, and nothing notably Fremen about any clothing or trinkets that could have been left where the body was dumped - how could anyone know if the body was Fremen?
Most likely, through Forensic Anthropology.
From that link:
Determination of Race from the Skeleton through Forensic
FORDISC, a computer program developed at the University of Tennessee,
is another metric technique reviewed that not only distinguishes
Whites, Blacks, and Native Americans but also male Hispanics, Chinese,
and Vietnamese. Platycnemia, femoral curvature and other morphological
attributes of the post-cranial skeleton may be used in support of a
racial determination; however, several investigators have turned to
post-cranial elements not only to use in support of cranial findings
but for use when cranial information is not available. As a result,
several discriminant functions from measurements of the pelvis, femur,
tibia or combinations of these elements have been developed. Accuracy
for these techniques varies from 57% to 95%, depending on the sample
and technique used. Other aspects of the femur, such as the diameter
of the neck, height of the intercondylar notch and femoral curvature,
have been measured for assessment of race.
So it is possible to read a partial skeleton for a racial "fingerprint" even with our technology today. I'd imagine it would be a simple matter for a Suk doctor to study the skeletal remains and note some unique Fremen features.
So that would have to be the answer, since bones were really all that was left at that point.